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 study elliptic curves over quadratic fields with isogenies of certain degrees. Let $n$ be a positive integer such that the modular curve $X_{0}(n)$ is hyperelliptic of genus ${\geqslant}2$ and such that its Jacobian has rank $0$ over $\mathbb{Q}$. We determine all points of $X_{0}(n)$ defined over quadratic fields, and we give a moduli interpretation of these points. We show that, with a finite number of exceptions up to $\overline{\mathbb{Q}}$-isomorphism, every elliptic curve over a quadratic field $K$ admitting an $n$-isogeny is $d$-isogenous, for some $d\mid n$, to the twist of its Galois conjugate by a quadratic extension $L$ of $K$. We determine $d$ and $L$ explicitly, and we list all exceptions. As a consequence, again with a finite number of exceptions up to $\overline{\mathbb{Q}}$-isomorphism, all elliptic curves with $n$-isogenies over quadratic fields are in fact $\mathbb{Q}$-curves.

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.

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.

We describe the “Deep Thought” algorithm, which can, among other things, take a commutator presentation for a finitely generated torsion-free nilpotent group G, and produce explicit polynomials for the multiplication of elements of G. These polynomials were first shown to exist by Philip Hall, and allow for “symbolic collection” in finitely generated nilpotent groups. We discuss various practicalissues in calculations in such groups, including the construction of a hybrid collector, making use of both the polynomials and ordinary collection from the left.

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.

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}$.

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.

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.

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.

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.

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.

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.

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.

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 construct an elliptic curve over the field of rational functions with torsion group $\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/4\mathbb{Z}$ and rank equal to four, and an elliptic curve over $\mathbb{Q}$ with the same torsion group and rank nine. Both results improve previous records for ranks of curves of this torsion group. They are obtained by considering elliptic curves induced by Diophantine triples.

Computational Galois theory, in particular the problem of computing the Galois group of a given polynomial, is a very old problem. Currently, the best algorithmic solution is Stauduhar’s method. Computationally, one of the key challenges in the application of Stauduhar’s method is to find, for a given pair of groups $H<G$, a $G$-relative $H$-invariant, that is a multivariate polynomial $F$ that is $H$-invariant, but not $G$-invariant. While generic, theoretical methods are known to find such $F$, in general they yield impractical answers. We give a general method for computing invariants of large degree which improves on previous known methods, as well as various special invariants that are derived from the structure of the groups. We then apply our new invariants to the task of computing the Galois groups of polynomials over the rational numbers, resulting in the first practical degree independent algorithm.

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.