Deterministic elliptic curve primality proving for a special sequence of numbers
From MaRDI portal
Publication:2949482
Abstract: We give a deterministic algorithm that very quickly proves the primality or compositeness of the integers N in a certain sequence, using an elliptic curve E/Q with complex multiplication by the ring of integers of Q(sqrt(-7)). The algorithm uses O(log N) arithmetic operations in the ring Z/NZ, implying a bit complexity that is quasi-quadratic in log N. Notably, neither of the classical "N-1" or "N+1" primality tests apply to the integers in our sequence. We discuss how this algorithm may be applied, in combination with sieving techniques, to efficiently search for very large primes. This has allowed us to prove the primality of several integers with more than 100,000 decimal digits, the largest of which has more than a million bits in its binary representation. At the time it was found, it was the largest proven prime N for which no significant partial factorization of N-1 or N+1 is known.
Recommendations
Cited in
(8)- Algorithmic Number Theory
- Explicit Isogenies of Prime Degree Over Quadratic Fields
- Finding suitable paths for the elliptic curve primality proving algorithm
- A framework for deterministic primality proving using elliptic curves with complex multiplication
- Some remarks on primality proving and elliptic curves
- Primes generated by elliptic curves
- Primality proving using elliptic curves with complex multiplication by imaginary quadratic fields of class number three
- scientific article; zbMATH DE number 177027 (Why is no real title available?)
This page was built for publication: Deterministic elliptic curve primality proving for a special sequence of numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2949482)
