elliptic curve primality proving

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. 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 , in 1993. 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.

Previously-known prime-proving methods such as the Pocklington primality test required at least partial factorization of $N \pm 1$ in order to prove that $N$ is prime. As a result, these methods required some luck and are generally slow in practice.

Elliptic curve primality proving

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:
:$O((\log n)^)\,$

for some $\varepsilon > 0$. This exponent may be decreased to $4+\varepsilon$ for some versions by heuristic arguments. ECPP works the same way as most other primality tests do, finding a group and showing its size is such that $p$ is prime. For ECPP the group is an elliptic curve over a finite set of quadratic forms such that $p-1$ is trivial to factor over the group.

ECPP generates an Atkin–Goldwasser–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.

, the largest prime that has been proved with ECPP method is $10^+65859$. The certification was performed by Andreas Enge using his fastECPP software ''CM''.

Proposition

The elliptic curve primality tests are based on criteria analogous to the Pocklington criterion, on which that test is based, Washington, Lawrence C., Elliptic Curves: Number Theory and Cryptography, Chapman & Hall/CRC, 2003 where the group
$(\Z/n\Z)^*$ is replaced by $E(\Z/n\Z),$ and ''E'' is a properly chosen elliptic curve. We will now state a proposition on which to base our test, which is analogous to the Pocklington criterion, and gives rise to the Goldwasser–Kilian–Atkin form of the elliptic curve primality test.

Let ''N'' be a positive integer, and ''E'' be the set which is defined by the equation $y^2 = x^3 + ax + b \bmod.$ Consider ''E'' over $\Z/N\Z,$ use the usual addition law on ''E'', and write 0 for the neutral element on ''E''.

Let ''m'' be an integer. If there is a prime ''q'' which divides ''m'', and is greater than \left (\sqrt 1 \right )^2 and there exists a point ''P'' on ''E'' such that

(1) ''mP'' = 0

(2) (''m''/''q'')''P'' is defined and not equal to 0

Then ''N'' is prime.

Proof

If ''N'' is composite, then there exists a prime $p \le \sqrt$ that divides ''N''. Define $E_p$ as the elliptic curve defined by the same equation as ''E'' but evaluated modulo ''p'' rather than modulo ''N''. Define $m_p$ as the order of the group $E_p$. By Hasse's theorem on elliptic curves we know

: m_p \le p+1+2\sqrt = \left (\sqrt + 1 \right )^2 \le \left (\sqrt 1 \right )^2 < q

and thus $\gcd(q,m_p)=1$ and there exists an integer ''u'' with the property that

: $uq \equiv 1 \bmod.$

Let $P_p$ be the point ''P'' evaluated modulo ''p''. Thus, on $E_p$ we have

: $(m/q)P_p = uq(m/q)P_p = umP_p = 0,$

by (1), as $mP_p$ is calculated using the same method as ''mP'', except modulo ''p'' rather than modulo ''N'' (and $p \mid N$).

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:Koblitz, Neal, Introduction to Number Theory and Cryptography, 2nd Ed, Springer, 1994

:$(m/q)P_p \ne 0.$

Goldwasser–Kilian algorithm

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

Choose three integers at random, ''a, x, y'' and set

: $b \equiv y^2 - x^3 - ax \pmod$

Now ''P'' = (''x'',''y'') is a point on ''E'', where we have that ''E'' is defined by $y^2 = x^3 + ax + b$. Next we need an algorithm to count the number of points on ''E''. Applied to ''E'', this algorithm (Koblitz and others suggest Schoof's algorithm) produces a number ''m'' which is the number of points on curve ''E'' over F_''N'', provided ''N'' is prime. If the point-counting algorithm stops at an undefined expression this allows to determine a non-trivial factor of ''N''. If it succeeds, we apply a criterion for deciding whether our curve ''E'' is acceptable.

If we can write ''m'' in the form $m = kq$ where $k \ge 2$ is a small integer and ''q'' a large probable prime (a number that passes a probabilistic primality test, for example), then we do not discard ''E''. Otherwise, we discard our curve and randomly select another triple ''(a, x, y)'' to start over. The idea here is to find an ''m'' that is divisible by a large prime number ''q''. This prime is a few digits smaller than ''m'' (or ''N'') so ''q'' will be easier to prove prime than ''N''.

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.

If $mP \neq 0$ it is clear that ''N'' is not prime, because if ''N'' were prime then ''E'' would have order ''m'', and any element of ''E'' would become 0 on multiplication by ''m''. If ''kP'' = 0, then the algorithm discards ''E'' and starts over with a different ''a, x, y'' triple.

Now if $mP = 0$ and $kP \neq 0$ then our previous proposition tells us that ''N'' is prime. However, there is one possible problem, which is the primality of ''q''. This is verified using the same algorithm. So we have described a recursive algorithm, where the primality of ''N'' depends on the primality of ''q'' and indeed smaller 'probable primes' until some threshold is reached where ''q'' is considered small enough to apply a non-recursive deterministic algorithm.

Problems with the algorithm

Atkin and Morain state "the problem with GK is that Schoof's algorithm seems almost impossible to implement." 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.Lenstra, Hendrik W., ''Efficient Algorithms in Number Theory'', https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf These comments have
to be seen in the historical context, before the improvements by Elkies and Atkin to Schoof's method.

A second problem Koblitz notes is the difficulty of finding the curve ''E'' whose number of points is of the form ''kq'', as above. There is no known theorem which guarantees we can find a suitable ''E'' in polynomially many attempts. The distribution of primes on the Hasse interval
+1-2\sqrt,p+1+2\sqrt/math>,
which contains ''m'', is not the same as the distribution of primes in the group orders, counting curves with multiplicity. However, this is not a significant problem in practice.

Atkin–Morain elliptic curve primality test (ECPP)

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:

Utilization of complex multiplication requires a negative discriminant, ''D'', such that ''D'' can be written as the product of two elements $D = \pi \bar$, or completely equivalently, we can write the equation:

: $a^2 + , D, b^2 = 4N \,$

For some ''a, b''. If we can describe ''N'' in terms of either of these forms, we can create an elliptic curve ''E'' on $\mathbb/N\mathbb$ with complex multiplication (described in detail below), and the number of points is given by:

: $, E(\mathbb/N\mathbb), = N + 1 - \pi - \bar = N + 1 - a. \,$

For ''N'' to split into the two elements, we need that $\left(\frac\right) = 1$ (where $\left(\frac\right)$ denotes the Legendre symbol). This is a necessary condition, and we achieve sufficiency if the class number ''h''(''D'') of the order in $\mathbb(\sqrt)$ is 1. This happens for only 13 values of ''D'', which are the elements of

The test

Pick discriminants ''D'' in sequence of increasing ''h''(''D''). For each ''D'' check if $\left(\frac\right) = 1$ and whether 4''N'' can be written as:

: $a^2 + , D, b^2 = 4N \,$

This part can be verified using Cornacchia's algorithm