Implementing the asymptotically fast version of the elliptic curve primality proving algorithm
From MaRDI portal
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.
Recommendations
Cites work
- Advances in Cryptology - CRYPTO 2003
- Algorithmic Number Theory
- Class invariants by Shimura's reciprocity law
- Computation of class numbers of quadratic number fields
- Cornacchia's algorithm
- Elliptic Curves and Primality Proving
- Elliptic Curves with a Given Number of Points
- Fast convolutions meet Montgomery
- Fast Decomposition of Polynomials with Known Galois Group
- scientific article; zbMATH DE number 1186935 (Why is no real title available?)
- scientific article; zbMATH DE number 1186963 (Why is no real title available?)
- scientific article; zbMATH DE number 1142300 (Why is no real title available?)
- scientific article; zbMATH DE number 3433971 (Why is no real title available?)
- scientific article; zbMATH DE number 2086888 (Why is no real title available?)
- scientific article; zbMATH DE number 2086890 (Why is no real title available?)
- scientific article; zbMATH DE number 2123628 (Why is no real title available?)
- scientific article; zbMATH DE number 2206373 (Why is no real title available?)
- Modern computer algebra
- Modular curves of composite level
- On distinguishing prime numbers from composite numbers
- Points S-entiers des courbes elliptiques. (S-integral points of elliptic curves)
- Primality Testing and Jacobi Sums
- Primality testing using elliptic curves
- PRIMES is in P
- Sharpening ``Primes is in P for a large family of numbers
- Solvability by radicals from an algorithmic point of view
- The complexity of class polynomial computation via floating point approximations
- Weber's class invariants revisited
Cited in
(20)- Elliptic periods and primality proving
- Modular curves over number fields and ECM
- A framework for deterministic primality proving using elliptic curves with complex multiplication
- Efficient CM-constructions of elliptic curves over finite fields
- scientific article; zbMATH DE number 1186935 (Why is no real title available?)
- Odd prime values of the Ramanujan tau function
- scientific article; zbMATH DE number 6941977 (Why is no real title available?)
- On the computation of class polynomials with ``thetanullwerte`` and its applications to the unit group computation
- 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
- Primality proofs with elliptic curves: heuristics and analysis
- Primality proofs with elliptic curves: experimental data
- Producing class numbers for the Atkin-Morain primality test
- Algorithmic Number Theory
- Numerical and statistical analysis of aliquot sequences
- FastECPP over MPI
- Schertz style class invariants for higher degree CM fields
- A strategy for elliptic curve primality proving
- Computing the cardinality of CM elliptic curves using torsion points
- There are infinitely many Perrin pseudoprimes
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)
