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 (12)

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

This page was built for publication: Implementing the asymptotically fast version of the elliptic curve primality proving algorithm