Elliptic curve primality

In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving.[1] It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and François Morain [de], in 1993.[2] The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing (and proving) followed quickly.

Primality testing is a field that has been around since the time of Fermat, in whose time most algorithms were based on factoring, which become unwieldy with large input; modern algorithms treat the problems of determining whether a number is prime and what its factors are separately. It became of practical importance with the advent of modern cryptography. Although many current tests result in a probabilistic output (N is either shown composite, or probably prime, such as with the Baillie–PSW primality test or the Miller–Rabin test), the elliptic curve test proves primality (or compositeness) with a quickly verifiable certificate.[3]

It is a general-purpose algorithm, meaning it does not depend on the number being of a special form. ECPP is currently in practice the fastest known algorithm for testing the primality of general numbers, but the worst-case execution time is not known. ECPP heuristically runs in time:

ECPP generates an AtkinGoldwasser–Kilian–Morain certificate of primality by recursion and then attempts to verify the certificate. The step that takes the most CPU time is the certificate generation, because factoring over a class field must be performed. The certificate can be verified quickly, allowing a check of operation to take very little time.

As of February 2020, the largest prime that has been proved with ECPP method is the partition number p(1289844341), which has 40,000 digits.[5] The certification by Paul Underwood took 21.5 months using Marcel Martin's Primo software.

This contradicts (2), because if (m/q)P is defined and not equal to 0 (mod N), then the same method calculated modulo p instead of modulo N will yield:[8]

From this proposition an algorithm can be constructed to prove an integer, N, is prime. This is done as follows:[6]

Assuming we find a curve which passes the criterion, proceed to calculate mP and kP. If any of the two calculations produce an undefined expression, we can get a non-trivial factor of N. If both calculations succeed, we examine the results.

Atkin and Morain state "the problem with GK is that Schoof's algorithm seems almost impossible to implement."[3] It is very slow and cumbersome to count all of the points on E using Schoof's algorithm, which is the preferred algorithm for the Goldwasser–Kilian algorithm. However, the original algorithm by Schoof is not efficient enough to provide the number of points in short time.[11] These comments have to be seen in the historical context, before the improvements by Elkies and Atkin to Schoof's method.

In a 1993 paper, Atkin and Morain described an algorithm ECPP which avoided the trouble of relying on a cumbersome point counting algorithm (Schoof's). The algorithm still relies on the proposition stated above, but rather than randomly generating elliptic curves and searching for a proper m, their idea was to construct a curve E where the number of points is easy to compute. Complex multiplication is key in the construction of the curve.

Now, given an N for which primality needs to be proven we need to find a suitable m and q, just as in the Goldwasser–Kilian test, that will fulfill the proposition and prove the primality of N. (Of course, a point P and the curve itself, E, must also be found.)

ECPP uses complex multiplication to construct the curve E, doing so in a way that allows for m (the number of points on E) to be easily computed. We will now describe this method:

use the complex multiplication method to construct the curve E and a point P on it. Then we can use our proposition to verify the primality of N. Note that if m does not have a large prime factor or cannot be factored quickly enough, another choice of D can be made.[1]

For completeness, we will provide an overview of complex multiplication, the way in which an elliptic curve can be created, given our D (which can be written as a product of two elements).

Given a root j there are only two possible nonisomorphic choices of E, one for each choice of r. We have the cardinality of these curves as

Just as with the Goldwasser–Killian test, this one leads to a down-run procedure. Again, the culprit is q. Once we find a q that works, we must check it to be prime, so in fact we are doing the whole test now for q. Then again we may have to perform the test for factors of q. This leads to a nested certificate where at each level we have an elliptic curve E, an m and the prime in doubt, q.

If s satisfies the inequality, and its prime factors satisfy the above, then N is prime.

But before we can do this, we must construct our curve, and choose a point P. In order to construct the curve, we make use of complex multiplication. In our case we compute the J-invariant

It is simple to check that 13(6, 6) = (12, 65) and 11P = (140, 147), and so, by Morain's proposition, N is prime.

Goldwasser and Kilian's elliptic curve primality proving algorithm terminates in expected polynomial time for at least

Now consider another conjecture, which will give us a bound on the total time of the algorithm.

Then the Goldwasser Kilian algorithm proves the primality of N in an expected time of

In (1), an elliptic curve, E is picked, along with a point Q on E, such that the x-coordinate of Q is a quadratic nonresidue. We can say

There is an algorithm as well for when n is large; however, for this we refer to the aforementioned article.[16]