Andreas Enge

We analyse and compare the complexity of several algorithms for computing modular polynomials. Under the assumption that rounding errors do not influence the correctness of the result, which appears to be satisfied in practice, we show that an algorithm relying on floating point evaluation of modular functions and on interpolation has a complexity that is up to logarithmic factors linear in the size of the computed polynomials. In particular, it obtains the classical modular polynomial Φ ℓ \Phi _\ell of prime level ℓ \ell in time \[ O ( ℓ 2 log 3 ⁡ ℓ M ( ℓ ) ) ⊆ O ( ℓ 3 log 4 + ε ⁡ ℓ ) , O \left (\ell ^2 \log ^3 \ell M (\ell ) \right ) \subseteq O \left ( \ell ^3 \log ^{4 + \varepsilon }\ell \right ), \] where M ( ℓ ) M(\ell ) is the time needed to multiply two ℓ \ell -bit numbers. Besides treating modular polynomials for Γ 0 ( ℓ ) \Gamma ^0 (\ell ) , which are an important ingredient in many algorithms dealing with isogenies of elliptic curves, the algorithm is easily adapted to more general situations. Composite levels are handled just as easily as prime levels, as well as polynomials between a modular function and its transform of prime level, such as the Schläfli polynomials and their generalisations. Our distributed implementation of the algorithm confirms the theoretical analysis by computing modular equations of record level around 10000 10000 in less than two weeks on ten processors.

We analyse the complexity of computing class polynomials, that are an important ingredient for CM constructions of elliptic curves, via complex floating point approximations of their roots. The heart of the algorithm is the evaluation of modular functions in several arguments. The fastest one of the presented approaches uses a technique devised by Dupont to evaluate modular functions by Newton iterations on an expression involving the arithmetic-geometric mean. Under the heuristic assumption, justified by experiments, that the correctness of the result is not perturbed by rounding errors, the algorithm runs in time \[ O ( | D | log 3 ⁡ | D | M ( | D | log 2 ⁡ | D | ) ) ⊆ O ( | D | log 6 + ε ⁡ | D | ) ⊆ O ( h 2 + ε ) O \left ( \sqrt {|D|} \log ^3 |D| \, M \left ( \sqrt {|D|} \log ^2 |D| \right ) \right ) \subseteq O \left (|D| \log ^{6 + \varepsilon } |D| \right ) \subseteq O \left ( h^{2 + \varepsilon } \right ) \] for any ε > 0 \varepsilon > 0 , where D D is the CM discriminant, h h is the degree of the class polynomial and M ( n ) M (n) is the time needed to multiply two n n -bit numbers. Up to logarithmic factors, this running time matches the size of the constructed polynomials. The estimate also relies on a new result concerning the complexity of enumerating the class group of an imaginary quadratic order and on a rigorously proven upper bound for the height of class polynomials.

We present two algorithms for the arithmetic of cubic curves with a totally ramified prime at infinity. The first algorithm, inspired by Cantor’s reduction for hyperelliptic curves, is easily implemented with a few lines of code, making use of a polynomial arithmetic package. We prove explicit reducedness criteria for superelliptic curves of genus 3 and 4, which show the correctness of the algorithm. The second approach, quite general in nature and applicable to further classes of curves, uses the FGLM algorithm for switching between Gröbner bases for different orderings. Carrying out the computations symbolically, we obtain explicit reduction formulae in terms of the input data.