We study weak convergence of an Euler scheme for nonlinear stochastic delay differential equations (SDDEs) driven by multidimensional Brownian motion. The Euler scheme has weak order of convergence 1, as in the case of stochastic ordinary differential equations (SODEs) (i.e., without delay). The result holds for SDDEs with multiple finite fixed delays in the drift and diffusion terms. Although the set-up is non-anticipating, our approach uses the Malliavin calculus and the anticipating stochastic analysis techniques of Nualart and Pardoux.

Morgan Ward pursued the study of elliptic divisibility sequences, originally initiated by Lucas, and Chudnovsky and Chudnovsky subsequently suggested looking at elliptic divisibility sequences for prime appearance. The problem of prime appearance in these sequences is examined here, from both a theoretical and a practical viewpoint. We show calculations, together with a heuristic argument, to suggest that these sequences contain only finitely many primes.

This paper contains corrections to the tables of low-dimensional representations of quasi-simple groups published in the paper, ‘Low-dimensional representations of quasi-simple groups’, LMS Journal of Computation and Mathematics 4 (2001) 22–63.

We present p-adic algorithms for computing Hecke polynomials and Hecke eigenforms associated to spaces of classical modular forms, using the theory of overconvergent modular forms. The algorithms have a running time which grows linearly with the logarithm of the weight and are well suited to investigating the dimension variation of certain p-adically defined spaces of classical modular forms.

Due to the increasing application of fractional calculus in engineering and biomedical processes, we analyze a new method for the numerical simulation of a large class of coupled systems of fractional-order partial differential equations. In this paper, we study shifted Jacobi polynomials in the case of two variables and develop some new operational matrices of fractional-order integrations as well as fractional-order differentiations. By the use of these operational matrices, we present a new and easy method for solving a generalized class of coupled systems of fractional-order partial differential equations subject to some initial conditions. We convert the system under consideration to a system of easily solvable algebraic equation without discretizing the system, and obtain a highly accurate solution. Also, the proposed method is compared with some other well-known differential transform methods. The proposed method is computer oriented. We use MatLab to perform the necessary calculation. The next two parts will appear soon.

Let $k$ be a locally compact complete field with respect to a discrete valuation $v$. Let $ \mathcal{O} $ be the valuation ring, $\mathfrak{m}$ the maximal ideal and $F(x)\in \mathcal{O} [x] $ a monic separable polynomial of degree $n$. Let $\delta = v(\mathrm{Disc} (F))$. The Montes algorithm computes an OM factorization of $F$. The single-factor lifting algorithm derives from this data a factorization of $F(\mathrm{mod~} {\mathfrak{m}}^{\nu } )$, for a prescribed precision $\nu $. In this paper we find a new estimate for the complexity of the Montes algorithm, leading to an estimation of $O({n}^{2+ \epsilon } + {n}^{1+ \epsilon } {\delta }^{2+ \epsilon } + {n}^{2} {\nu }^{1+ \epsilon } )$ word operations for the complexity of the computation of a factorization of $F(\mathrm{mod~} {\mathfrak{m}}^{\nu } )$, assuming that the residue field of $k$ is small.

We present a quasi-linear iterative method for solving a system of $m$-nonlinear coupled differential equations. We provide an error analysis of the method to study its convergence criteria. In order to show the efficiency of the method, we consider some computational examples of this class of problem. These examples validate the accuracy of the method and show that it gives results which are convergent to the exact solutions. We prove that the method is accurate, fast and has a reasonable rate of convergence by computing some local and global error indicators.

This paper is concerned with a relation of Darboux in enumerative geometry, which has very useful applications in the study of polynomial vector fields. The original statement of Darboux was not correct. The present paper gives two different elementary proofs of this relation. The first one follows the ideas of Darboux, and uses basic facts about the intersection index of two plane algebraic curves; the second proof is rather more sophisticated, and gives a stronger result, which should also be very useful. The power of the relation of Darboux is then illustrated by the provision of new, simple proofs of two known results. First, it is shown that an irreducible invariant algebraic curve of degree n > 1 without multiple points for a polynomial vector field of degree m satisfies n ≤ m + 1. Second, a proof is given that quadratic polynomial vector fields have no algebraic limit cycles of degree 3.

We give the complete list of possible torsion subgroups of elliptic curves with complex multiplication over number fields of degree 1–13. Additionally we describe the algorithm used to compute these torsion subgroups and its implementation.

Given a prime q and a negative discriminant D, the CM method constructs an elliptic curve E/Fq by obtaining a root of the Hilbert class polynomial HD(X) modulo q. We consider an approach based on a decomposition of the ring class field defined by HD, which we adapt to a CRT setting. This yields two algorithms, each of which obtains a root of HD mod q without necessarily computing any of its coefficients. Heuristically, our approach uses asymptotically less time and space than the standard CM method for almost all D. Under the GRH, and reasonable assumptions about the size of log q relative to ∣D∣, we achieve a space complexity of O((m+n)log q) bits, where mn=h(D) , which may be as small as O(∣D∣1/4 log q) . The practical efficiency of the algorithms is demonstrated using ∣D∣>1016 and q≈2256, and also ∣D∣>1015 and q≈233220. These examples are both an order of magnitude larger than the best previous results obtained with the CM method.

NTRU is a public-key cryptosystem introduced at ANTS-III. The two most used techniques in attacking the NTRU private key are meet-in-the-middle attacks and lattice-basis reduction attacks. Howgrave-Graham combined both techniques in 2007 and pointed out that the largest obstacle to attacks is the memory capacity that is required for the meet-in-the-middle phase. In the present paper an algorithm is presented that applies low-memory techniques to find ‘golden’ collisions to Odlyzko’s meet-in-the-middle attack against the NTRU private key. Several aspects of NTRU secret keys and the algorithm are analysed. The running time of the algorithm with a maximum storage capacity of $w$ is estimated and experimentally verified. Experiments indicate that decreasing the storage capacity $w$ by a factor $1<c<\sqrt{w}$ increases the running time by a factor $\sqrt{c}$.

Let G be a simple algebraic group over an algebraically closed field with Lie algebra g. Then the orbits of nilpotent elements of g under the adjoint action of G have been classified. We describe a simple algorithm for finding a representative of a nilpotent orbit. We use this to compute lists of representatives of these orbits for the Lie algebras of exceptional type. Then we give two applications. The first one concerns settling a conjecture by Elashvili on the index of centralizers of nilpotent orbits, for the case where the Lie algebra is of exceptional type. The second deals with minimal dimensions of centralizers in centralizers.

We perform an almost sure linear stability analysis of the θ-Maruyama method, selecting as our test equation a two-dimensional system of Itô differential equations with diagonal drift coefficient and two independent stochastic perturbations which capture the stabilising and destabilising roles of feedback geometry in the almost sure asymptotic stability of the equilibrium solution. For small values of the constant step-size parameter, we derive close-to-sharp conditions for the almost sure asymptotic stability and instability of the equilibrium solution of the discretisation that match those of the original test system. Our investigation demonstrates the use of a discrete form of the Itô formula in the context of an almost sure linear stability analysis.

In this paper we study the discrete logarithm problem in medium- and high-characteristic finite fields. We propose a variant of the number field sieve (NFS) based on numerous number fields. Our improved algorithm computes discrete logarithms in $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}\mathbb{F}_{p^n}$ for the whole range of applicability of the NFS and lowers the asymptotic complexity from $L_{p^n}({1/3},({128/9})^{1/3})$ to $L_{p^n}({1/3},(2^{13}/3^6)^{1/3})$ in the medium-characteristic case, and from $L_{p^n}({1/3},({64/9})^{1/3})$ to $L_{p^n}({1/3},((92 + 26 \sqrt{13})/27)^{1/3})$ in the high-characteristic case.

We describe how the Hardy–Ramanujan–Rademacher formula can be implemented to allow the partition function p(n) to be computed with softly optimal complexity O(n1/2+o(1)) and very little overhead. A new implementation based on these techniques achieves speedups in excess of a factor 500 over previously published software and has been used by the author to calculate p(1019), an exponent twice as large as in previously reported computations. We also investigate performance for multi-evaluation of p(n), where our implementation of the Hardy–Ramanujan–Rademacher formula becomes superior to power series methods on far denser sets of indices than previous implementations. As an application, we determine over 22 billion new congruences for the partition function, extending Weaver’s tabulation of 76 065 congruences. Supplementary materials are available with this article.

From power series expansions of functions on curves over finite fields, one can obtain sequences with perfect or almost perfect linear complexity profile. It has been suggested by various authors to use such sequences as key streams for stream ciphers. In this work, we show how long parts of such sequences can be computed efficiently from short ones. Such sequences should therefore be considered to be cryptographically weak. Our attack leads in a natural way to a new measure of the complexity of sequences which we call expansion complexity.

Two semigroups are distinct if they are neither isomorphic nor anti-isomorphic. Although there exist $15\,973$ pairwise distinct semigroups of order six, only four are known to be non-finitely based. In the present article, the finite basis property of the other $15\,969$ distinct semigroups of order six is verified. Since all semigroups of order five or less are finitely based, the four known non-finitely based semigroups of order six are the only examples of minimal order.

In this paper, the authors analyze the Gaudry-Hess-Smart (GHS) Weil descent attack on the elliptic curve discrete logarithm problem (ECDLP) for elliptic curves defined over characteristic two finite fields of composite extension degree. For each such field F2N, where N is in [100,600], elliptic curve parameters are identified such that: (i) there should exist a cryptographically interesting elliptic curve E over F2N with these parameters; and (ii) the GHS attack is more efficient for solving the ECDLP in E(F2N) than for solving the ECDLP on any other cryptographically interesting elliptic curve over F2N. The feasibility of the GHS attack on the specific elliptic curves is examined over F2176, F2208, F2272, F2304 and F2368, which are provided as examples in the ANSI X9.62 standard for the elliptic curve signature scheme ECDSA. Finally, several concrete instances are provided of the ECDLP over F2N, N composite, of increasing difficulty; these resist all previously known attacks, but are within reach of the GHS attack.

Given a sextic CM field $K$, we give an explicit method for finding all genus-$3$ hyperelliptic curves defined over $\mathbb{C}$ whose Jacobians are simple and have complex multiplication by the maximal order of this field, via an approximation of their Rosenhain invariants. Building on the work of Weng [J. Ramanujan Math. Soc. 16 (2001) no. 4, 339–372], we give an algorithm which works in complete generality, for any CM sextic field $K$, and computes minimal polynomials of the Rosenhain invariants for any period matrix of the Jacobian. This algorithm can be used to generate genus-3 hyperelliptic curves over a finite field $\mathbb{F}_{p}$ with a given zeta function by finding roots of the Rosenhain minimal polynomials modulo $p$.

We present an algorithm that reduces the problem of calculating a numerical approximation to the action of absolute Frobenius on the middle-dimensional rigid cohomology of a smooth projective variety over a finite held, to that of performing the same calculation for a smooth hyperplane section. When combined with standard geometric techniques, this yields a method for computing zeta functions which proceeds ‘by induction on the dimension’. The ‘inductive step’ combines previous work of the author on the deformation of Frobenius with a higher rank generalisation of Kedlaya's algorithm. The analysis of the loss of precision during the algorithm uses a deep theorem of Christol and Dwork on p-adic solutions to differential systems at regular singular points. We apply our algorithm to compute the zeta functions of compactifications of certain surfaces which are double covers of the affine plane.