Deterministic elliptic curve primality proving for a special sequence of numbers
From MaRDI portal
Publication:2949482
zbMATH Open1344.11082arXiv1202.3695MaRDI QIDQ2949482FDOQ2949482
Authors: Alexander Abatzoglou, Andrew V. Sutherland, Angela Wong, Alice Silverberg 
Publication date: 1 October 2015
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.
Full work available at URL: https://arxiv.org/abs/1202.3695
Recommendations
Cited In (8)
- Title not available (Why is that?)
- Primality proving using elliptic curves with complex multiplication by imaginary quadratic fields of class number three
- Some remarks on primality proving and elliptic curves
- Finding suitable paths for the elliptic curve primality proving algorithm
- Explicit Isogenies of Prime Degree Over Quadratic Fields
- A framework for deterministic primality proving using elliptic curves with complex multiplication
- Algorithmic Number Theory
- Primes generated by elliptic curves
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)
