Implementing the asymptotically fast version of the elliptic curve primality proving algorithm

DOI10.1090/S0025-5718-06-01890-4zbMath1127.11084arXivmath/0502097OpenAlexW2060377935WikidataQ56059199 ScholiaQ56059199MaRDI QIDQ3420443

François Morain

Publication date: 2 February 2007

Published in: Mathematics of Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0502097

zbMATH Keywords

computational complexitycomplex multiplicationprimality provingECPP algorithm

Mathematics Subject Classification ID

Elliptic curves over global fields (11G05) Number-theoretic algorithms; complexity (11Y16) Curves over finite and local fields (11G20) Complex multiplication and moduli of abelian varieties (11G15) Primality (11Y11)

Related Items

Odd prime values of the Ramanujan tau function, A strategy for elliptic curve primality proving, Computing the cardinality of CM elliptic curves using torsion points, On the Computation of Class Polynomials with “Thetanullwerte” and Its Applications to the Unit Group Computation, Elliptic periods and primality proving, There are infinitely many Perrin pseudoprimes, Efficient CM-constructions of elliptic curves over finite fields, A framework for deterministic primality proving using elliptic curves with complex multiplication, On the Evaluation of Singular Invariants for Canonical Generators of Certain Genus One Arithmetic Groups, Numerical and Statistical Analysis of Aliquot Sequences, Modular curves over number fields and ECM, An approach for computing generators of class fields of imaginary quadratic number fields using the Schwarzian derivative

Uses Software

• MPFR
• ECPP
• MPC

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On distinguishing prime numbers from composite numbers
• Weber's class invariants revisited
• PRIMES is in P
• Points S-entiers des courbes elliptiques. (S-integral points of elliptic curves)
• Class invariants by Shimura's reciprocity law
• Cornacchia's algorithm
• Solvability by radicals from an algorithmic point of view
• The complexity of class polynomial computation via floating point approximations
• Elliptic Curves and Primality Proving
• Computation of class numbers of quadratic number fields
• Primality testing using elliptic curves
• Primality Testing and Jacobi Sums
• Fast Decomposition of Polynomials with Known Galois Group
• Modular curves of composite level
• Sharpening ``Primes is in P for a large family of numbers
• Advances in Cryptology - CRYPTO 2003
• Fast convolutions meet Montgomery
• Algorithmic Number Theory
• Elliptic Curves with a Given Number of Points