Vol. 1, No. 1, 2013

Download this article
Download this article For screen
For printing
Recent Volumes
1: ANTS X
The Open Book Series
About the Series
Ethics Statement
Deterministic elliptic curve primality proving for a special sequence of numbers

Alexander Abatzoglou, Alice Silverberg, Andrew V. Sutherland and Angela Wong

Vol. 1 (2013), No. 1, 1–20
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 with complex multiplication by the ring of integers of (7). The algorithm uses O(logN) arithmetic operations in the ring N, implying a bit complexity that is quasiquadratic in logN. 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 (as of final submission it was second largest).

Keywords
primality, elliptic curves, complex multiplication
Mathematical Subject Classification 2010
Primary: 11Y11
Secondary: 11G05, 14K22
Milestones
Published: 14 November 2013
Authors
Alexander Abatzoglou
Department of Mathematics
University of California
Irvine, CA 92697
United States
Alice Silverberg
Mathematics Department
University of California
Irvine, CA 92697-3875
United States
Andrew V. Sutherland
Department of Mathematics
MIT
Cambridge, MA 02139
United States
Angela Wong
Department of Mathematics
University of California
Irvine, CA 92697
United States