Elliptic curve primality

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

${\displaystyle m_{p}\leq p+1+2{\sqrt {p}}=\left({\sqrt {p}}+1\right)^{2}\leq \left({\sqrt[{4}]{N}}+1\right)^{2}<q}$

and thus ${\displaystyle \gcd(q,m_{p})=1}$ and there exists an integer u with the property that

${\displaystyle uq\equiv 1{\bmod {m_{p}}}.}$

Let ${\displaystyle P_{p}}$ be the point P evaluated modulo p. Thus, on ${\displaystyle E_{p}}$ we have

${\displaystyle (m/q)P_{p}=uq(m/q)P_{p}=umP_{p}=0,}$

by (1), as ${\displaystyle mP_{p}}$ is calculated using the same method as mP, except modulo p rather than modulo N (and ${\displaystyle 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:[8]

${\displaystyle (m/q)P_{p}\neq 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 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 ${\displaystyle [p+1-2{\sqrt {p}},p+1+2{\sqrt {p}}]}$, 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.[8]

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

${\displaystyle a^{2}+|D|b^{2}=4N\,}$

This part can be verified using Cornacchia's algorithm. Once acceptable D and a have been discovered, calculate ${\displaystyle m=N+1-a}$. Now if m has a prime factor q of size

${\displaystyle q>(N^{1/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 ${\displaystyle D\neq -3}$ and ${\displaystyle D\neq -4}$ (these cases are much more easily done). It is necessary to calculate the elliptic j-invariants of the h(D) classes of the order of discriminant D as complex numbers. There are several formulas to calculate these.

Next create the monic polynomial ${\displaystyle H_{D}(X)}$, which has roots corresponding to the h(D) values. Note, that ${\displaystyle H_{D}(X)}$ is the class polynomial. From complex multiplication theory, we know that ${\displaystyle H_{D}(X)}$ has integer coefficients, which allows us to estimate these coefficients accurately enough to discover their true values.

Now, if N is prime, CM tells us that ${\displaystyle H_{D}(X)}$ splits modulo N into a product of h(D) linear factors, based on the fact that D was chosen so that N splits as the product of two elements. Now if j is one of the h(D) roots modulo N we can define E as:

${\displaystyle y^{2}=x^{3}-3kc^{2r}x+2kc^{3r},{\text{ where }}k={\frac {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

${\displaystyle |E(\mathbb {Z} /N\mathbb {Z} )|=N+1-a}$ or ${\displaystyle |E(\mathbb {Z} /N\mathbb {Z} )|=N+1+a}$[1][10][12]

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 ${\displaystyle N=167}$ is prime using the Atkin–Morain ECPP test. First proceed through the set of 13 possible discriminants, testing whether the Legendre Symbol ${\displaystyle (D/N)=1}$, and if 4N can be written as ${\displaystyle 4N=a^{2}+|D|b^{2}}$.

For our example ${\displaystyle D=-43}$ is chosen. This is because ${\displaystyle (D/N)=(-43/167)=1}$ and also, using Cornacchia's algorithm, we know that ${\displaystyle 4\cdot (167)=25^{2}+(43)(1^{2})}$ and thus a = 25 and b = 1.

The next step is to calculate m. This is easily done as ${\displaystyle m=N+1-a}$ which yields ${\displaystyle m=167+1-25=143.}$ Next we need to find a probable prime divisor of m, which was referred to as q. It must satisfy the condition that ${\displaystyle q>(N^{1/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, ${\displaystyle s>(N^{1/4}+1)^{2}}$, but is not necessarily prime, and check whether, for each ${\displaystyle p_{i}}$ which divides s

${\displaystyle (m/p_{i})P\neq P_{\infty }}$

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 ${\displaystyle p_{i}}$'s are 11 and 13. First, it is clear that ${\displaystyle 143>(167^{1/4}+1)^{2}}$, and so we need only check the values of

${\displaystyle (143/11)P=13P\qquad {\text{ and }}\qquad (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

${\displaystyle j\equiv -960^{3}{\pmod {167}}\equiv 107{\pmod {167}}.}$

Next we compute

${\displaystyle k={\frac {j}{1728-j}}{\pmod {167}}\equiv 158{\pmod {167}}}$

and we know our elliptic curve is of the form:

${\displaystyle y^{2}=x^{3}+3kc^{2}x+2kc^{3}}$,

where k is as described previously and c a non-square in ${\displaystyle \mathbb {F} _{167}}$. So we can begin with

${\displaystyle {\begin{aligned}r&=0\\3k&\equiv 140{\pmod {167}}\\2k&\equiv 149{\pmod {167}}\end{aligned}}}$

which yields

${\displaystyle E:y^{2}=x^{3}+140x+149{\pmod {167}}}$

Now, utilizing the point P = (6,6) on E it can be verified that ${\displaystyle 143P=P_{\infty }.}$

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

Let ${\displaystyle \pi (x)}$ be the number of primes smaller than x

${\displaystyle \exists c_{1},c_{2}>0:\pi (x+{\sqrt {x}})-\pi (x)\geq {\frac {c_{2}{\sqrt {x}}}{\log ^{c_{1}}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 ${\displaystyle O(k^{2})}$ that can be verified in ${\displaystyle O(k^{4})}$.[14]

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

Suppose there exist positive constants ${\displaystyle c_{1}}$ and ${\displaystyle c_{2}}$ such that the amount of primes in the interval

${\displaystyle [x,x+{\sqrt {2x}}],x\geq 2}$ is larger than ${\displaystyle c_{1}{\sqrt {x}}(\log x)^{-c_{2}}}$

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

${\displaystyle O(\log ^{10+c_{2}}n)}$[13]

For the Atkin–Morain algorithm, the running time stated is

${\displaystyle O((\log N)^{6+\epsilon })}$ for some ${\displaystyle \epsilon >0}$[3]

We take E as our elliptic curve, where E is of the form ${\displaystyle y^{2}=x^{3}-mx}$ for ${\displaystyle m\in \mathbb {Z} ,m\not \equiv 0{\bmod {p}},}$ where ${\displaystyle p\equiv 3{\bmod {4}}}$ is prime, and ${\displaystyle p+1=2^{k}n,}$ with ${\displaystyle k\in \mathbb {Z} ,k\geq 2,n}$ odd.

Theorem 1.[7] ${\displaystyle E(\mathbb {F} _{p})=p+1.}$

Theorem 2. ${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2^{k}n}}$ or ${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2}\oplus \mathbb {Z} _{2^{k-1}n}}$ depending on whether or not m is a quadratic residue modulo p.

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 ${\displaystyle 2^{k}}$ in the cyclic group ${\displaystyle E(\mathbb {F} _{p})\cong \mathbb {Z} _{2^{k}n}.}$

First we will present the case where n is relatively small with respect to ${\displaystyle 2^{k}}$, and this will require one more theorem:

Theorem 4. Choose a ${\displaystyle \lambda >1}$ and suppose

${\displaystyle n\leq {\frac {\sqrt {p}}{\lambda }}\qquad {\text{and}}\qquad \lambda {\sqrt {p}}>\left({\sqrt[{4}]{p}}+1\right)^{2}.}$

Then p is a prime if and only if there exists a Q = (x,y) on E, such that ${\displaystyle \gcd {(S_{i},p)}=1}$ for i = 1, 2, ...,k − 1 and ${\displaystyle S_{k}\equiv 0{\pmod {p}},}$ where ${\displaystyle S_{i}}$ is a sequence with initial value ${\displaystyle S_{0}=x}$.

We provide the following algorithm, which relies mainly on Theorems 3 and 4. To verify the primality of a given number ${\displaystyle N}$, perform the following steps:

(1) Choose ${\displaystyle x\in \mathbb {Z} }$ such that ${\displaystyle \left({\frac {x}{N}}\right)=-1}$, and find ${\displaystyle y\in \mathbb {Z} ,y\not \equiv 0{\pmod {2}}}$ such that ${\displaystyle \left({\frac {x^{3}-y^{2}}{N}}\right)=1}$.

Take ${\displaystyle m={\frac {x^{3}-y^{2}}{x}}\mod N}$ and ${\displaystyle m\not \equiv 0{\pmod {N}}}$.

Then ${\displaystyle Q'=(x,y)}$ is on ${\displaystyle E:y^{2}=x^{3}-mx}$.

Calculate ${\displaystyle Q=nQ'}$. If ${\displaystyle Q\in E}$ then ${\displaystyle N}$ is composite, otherwise proceed to (2).

(2) Set ${\displaystyle S_{i}}$ as the sequence with initial value ${\displaystyle Q}$. Calculate ${\displaystyle S_{i}}$ for ${\displaystyle i=}$${\displaystyle 1,2,3,...,k-1}$.

If ${\displaystyle \gcd({S_{i},N})>1}$ for an ${\displaystyle i}$, where ${\displaystyle 1\leq i\leq k-1}$ then ${\displaystyle N}$ is composite. Otherwise, proceed to (3).

(3) If ${\displaystyle S_{k}\equiv 0{\pmod {N}}}$ then ${\displaystyle N}$ is prime. Otherwise, ${\displaystyle N}$ is composite. This completes the test.

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

${\displaystyle \left({\frac {m}{N}}\right)=\left({\frac {\frac {x^{3}-y^{2}}{x}}{N}}\right)=\left({\frac {x}{N}}\right)\left({\frac {x^{3}-y^{2}}{N}}\right)=-1\cdot 1=-1.}$

Thus, if N is prime, Q' has order divisible by ${\displaystyle 2^{k}}$, by Theorem 3, and therefore the order of Q' is ${\displaystyle 2^{k}d}$ d | n.

This means Q = nQ' has order ${\displaystyle 2^{k}}$. Therefore, if (1) concludes that N is composite, it truly is composite. (2) and (3) check if Q has order ${\displaystyle 2^{k}}$. Thus, if (2) or (3) conclude N is composite, it is composite.

Now, if the algorithm concludes that N is prime, then that means ${\displaystyle S_{1}}$ satisfies the condition of Theorem 4, and so N is truly prime.

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