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, 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]
Previously-known prime-proving methods such as the Pocklington primality test required at least partial factorization of
N\pm1
N
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((logn)5+\varepsilon)
for some
\varepsilon>0
4+\varepsilon
p
p-1
ECPP generates an Atkin–Goldwasser–Kilian–Morain certificate of primality by recursion and thenattempts 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
5104824+1048245
The elliptic curve primality tests are based on criteria analogous to the Pocklington criterion, on which that test is based,[6] [7] where the group
(\Z/n\Z)*
E(\Z/n\Z),
Let N be a positive integer, and E be the set which is defined by the equation
y2=x3+ax+b\bmod{N}.
\Z/N\Z,
Let m be an integer. If there is a prime q which divides m, and is greater than
\left(\sqrt[4]{N}+1\right)2
(1) mP = 0
(2) (m/q)P is defined and not equal to 0
Then N is prime.
If N is composite, then there exists a prime
p\le\sqrt{N}
Ep
mp
Ep
mp\lep+1+2\sqrt{p}=\left(\sqrt{p}+1\right)2\le\left(\sqrt[4]{N}+1\right)2<q
and thus
\gcd(q,mp)=1
uq\equiv1\bmod{mp}.
Let
Pp
Ep
(m/q)Pp=uq(m/q)Pp=umPp=0,
by (1), as
mPp
p\midN
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]
(m/q)Pp\ne0.
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\equivy2-x3-ax\pmod{N}
Now P = (x,y) is a point on E, where we have that E is defined by
y2=x3+ax+b
If we can write m in the form
m=kq
k\ge2
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 ≠ 0
Now if
mP=0
kP ≠ 0
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 haveto 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
[p+1-2\sqrt{p},p+1+2\sqrt{p}]
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{\pi}
a2+|D|b2=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
Z/NZ
|E(Z/NZ)|=N+1-\pi-\bar{\pi}=N+1-a.
For N to split into the two elements, we need that
\left( | D |
N |
\right)=1
\left( | D |
N |
\right)
Q(\sqrt{D})
Pick discriminants D in sequence of increasing h(D). For each D check if
\left( | D |
N |
\right)=1
a2+|D|b2=4N
This part can be verified using Cornacchia's algorithm. Once acceptable D and a have been discovered, calculate
m=N+1-a
q>(N1/4+1)2
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).
Assume first that
D ≠ -3
D ≠ -4
Next create the monic polynomial
HD(X)
HD(X)
HD(X)
Now, if N is prime, CM tells us that
HD(X)
y2=x3-3kc2rx+2kc3r,wherek=
j | |
j-1728 |
,
c is any quadratic nonresidue mod N, and r is either 0 or 1.
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
|E(Z/NZ)|=N+1-a
|E(Z/NZ)|=N+1+a
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.
We construct an example to prove that
N=167
(D/N)=1
4N=a2+|D|b2
For our example
D=-43
(D/N)=(-43/167)=1
4 ⋅ (167)=252+(43)(12)
The next step is to calculate m. This is easily done as
m=N+1-a
m=167+1-25=143.
q>(N1/4+1)2.
In this case, m = 143 = 11×13. So unfortunately we cannot choose 11 or 13 as our q, for it does not satisfy the necessary inequality. We are saved, however, by an analogous proposition to that which we stated before the Goldwasser–Kilian algorithm, which comes from a paper by Morain.[13] It states, that given our m, we look for an s which divides m,
s>(N1/4+1)2
pi
(m/pi)P ≠ Pinfty
for some point P on our yet to be constructed curve.
If s satisfies the inequality, and its prime factors satisfy the above, then N is prime.
So in our case, we choose s = m = 143. Thus our possible
pi
143>(1671/4+1)2
(143/11)P=13P and (143/13)P=11P.
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
j\equiv-9603\pmod{167}\equiv107\pmod{167}.
Next we compute
k=
j | |
1728-j |
\pmod{167}\equiv158\pmod{167}
and we know our elliptic curve is of the form:
y2=x3+3kc2x+2kc3
where k is as described previously and c a non-square in
F167
\begin{align} r&=0\ 3k&\equiv140\pmod{167}\ 2k&\equiv149\pmod{167} \end{align}
which yields
E:y2=x3+140x+149\pmod{167}
Now, utilizing the point P = (6,6) on E it can be verified that
143P=Pinfty.
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
1-
| ||||
O\left(2 |
\right)
of prime inputs.
Let
\pi(x)
\existsc1,c2>0:\pi(x+\sqrt{x})-\pi(x)\ge
c2\sqrt{x | |
for sufficiently large x.
If one accepts this conjecture then the Goldwasser–Kilian algorithm terminates in expected polynomial time for every input. Also, if our N is of length k, then the algorithm creates a certificate of size
O(k2)
O(k4)
Now consider another conjecture, which will give us a bound on the total time of the algorithm.
Suppose there exist positive constants
c1
c2
[x,x+\sqrt{2x}],x\ge2
c1\sqrt{x}(log
-c2 | |
x) |
Then the Goldwasser Kilian algorithm proves the primality of N in an expected time of
10+c2 | |
O(log |
n)
For the Atkin–Morain algorithm, the running time stated is
O((logN)6+\epsilon)
\epsilon>0
For some forms of numbers, it is possible to find 'short-cuts' to a primality proof. This is the case for the Mersenne numbers. In fact, due to their special structure, which allows for easier verification of primality, the six largest known prime numbers are all Mersenne numbers.[15] There has been a method in use for some time to verify primality of Mersenne numbers, known as the Lucas–Lehmer test. This test does not rely on elliptic curves. However we present a result where numbers of the form
N=2kn-1
k,n\in\Z,k\ge2
2kn-1
We take E as our elliptic curve, where E is of the form
y2=x3-mx
m\in\Z,m\not\equiv0\bmod{p},
p\equiv3\bmod{4}
p+1=2kn,
k\in\Z,k\ge2,n
Theorem 1.[7]
|E(Fp)|=p+1.
Theorem 2.
E(Fp)\cong
\Z | |
2kn |
E(Fp)\cong\Z2 ⊕
\Z | |
2k-1n |
Theorem 3. Let Q = (x,y) on E be such that x a quadratic non-residue modulo p. Then the order of Q is divisible by
2k
E(Fp)\cong
\Z | |
2kn |
.
First we will present the case where n is relatively small with respect to
2k
Theorem 4. Choose a
λ>1
n\le
\sqrt{p | |
Then p is a prime if and only if there exists a Q = (x,y) on E, such that
\gcd{(Si,p)}=1
Sk\equiv0\pmod{p},
Si
S0=x
We provide the following algorithm, which relies mainly on Theorems 3 and 4. To verify the primality of a given number
N
(1) Choose
x\inZ
\left( | x |
N |
\right)=-1
y\inZ,y\not\equiv0\pmod{2}
\left( | x3-y2 |
N |
\right)=1
Take
m=
x3-y2 | |
x |
\modN
m\not\equiv0\pmod{N}
Then
Q'=(x,y)
E:y2=x3-mx
Calculate
Q=nQ'
Q\inE
N
(2) Set
Si
Q
Si
i=
1,2,3,...,k-1
If
\gcd({Si,N})>1
i
1\lei\lek-1
N
(3) If
Sk\equiv0\pmod{N}
N
N
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
\left( | m |
N |
\right)=\left(
| ||||
N |
\right)=\left(
x | \right)\left( | |
N |
x3-y2 | |
N |
\right)=-1 ⋅ 1=-1.
Thus, if N is prime, Q has order divisible by
2k
2kd
This means Q = nQ has order
2k
2k
Now, if the algorithm concludes that N is prime, then that means
S1
There is an algorithm as well for when n is large; however, for this we refer to the aforementioned article.[16]
2kn-1