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

DOI10.1090/S0025-5718-06-01890-4zbMATH Open1127.11084arXivmath/0502097OpenAlexW2060377935WikidataQ56059199 ScholiaQ56059199MaRDI QIDQ3420443FDOQ3420443

Authors: François Morain 

Publication date: 2 February 2007

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

Abstract: The elliptic curve primality proving (ECPP) algorithm is one of the current fastest practical algorithms for proving the primality of large numbers. Its running time cannot be proven rigorously, but heuristic arguments show that it should run in time O ((log N)^5) to prove the primality of N. An asymptotically fast version of it, attributed to J. O. Shallit, runs in time O ((log N)^4). The aim of this article is to describe this version in more details, leading to actual implementations able to handle numbers with several thousands of decimal digits.

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

Recommendations

• Algorithmic Number Theory
• Primality proofs with elliptic curves: heuristics and analysis
• A strategy for elliptic curve primality proving
• Elliptic Curves and Primality Proving
• A primality test algorithm using supersingular elliptic curves

zbMATH Keywords

computational complexitycomplex multiplicationprimality provingECPP algorithm

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (19)

• Primality proofs with elliptic curves: experimental data
• Modular curves over number fields and ECM
• Title not available (Why is that?)
• On the computation of class polynomials with ``thetanullwerte`` and its applications to the unit group computation
• Numerical and statistical analysis of aliquot sequences
• There are infinitely many Perrin pseudoprimes
• Elliptic periods and primality proving
• Producing class numbers for the Atkin-Morain primality test
• On the evaluation of singular invariants for canonical generators of certain genus one arithmetic groups
• An approach for computing generators of class fields of imaginary quadratic number fields using the Schwarzian derivative
• FastECPP over MPI
• A strategy for elliptic curve primality proving
• Primality proofs with elliptic curves: heuristics and analysis
• Efficient CM-constructions of elliptic curves over finite fields
• Title not available (Why is that?)
• Computing the cardinality of CM elliptic curves using torsion points
• A framework for deterministic primality proving using elliptic curves with complex multiplication
• Algorithmic Number Theory
• Odd prime values of the Ramanujan tau function

Uses Software

• MPFR
• ECPP
• MPC

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3420443)