Elliptic curve primality

Last updated

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.

Contents

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 in order to prove that 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:

for some . [4] This exponent may be decreased to 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 is prime. For ECPP the group is an elliptic curve over a finite set of quadratic forms such that is trivial to factor over the group.

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 May 2023, the largest prime that has been proved with ECPP method is . [5] 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, [6] [7] where the group is replaced by 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 Consider E over 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 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 that divides N. Define as the elliptic curve defined by the same equation as E but evaluated modulo p rather than modulo N. Define as the order of the group . By Hasse's theorem on elliptic curves we know

and thus and there exists an integer u with the property that

Let be the point P evaluated modulo p. Thus, on we have

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

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]

Goldwasser–Kilian algorithm

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

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

Now P = (x,y) is a point on E, where we have that E is defined by . 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 FN, 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 where 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 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 and 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. [9] [10]

Problems with the algorithm

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 , 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]

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 , or completely equivalently, we can write the equation:

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

For N to split into the two elements, we need that (where denotes the Legendre symbol). This is a necessary condition, and we achieve sufficiency if the class number h(D) of the order in is 1. This happens for only 13 values of D, which are the elements of {−3, −4, −7, −8, −11, −12, −16, −19, −27, −28, −43, −67, −163}

The test

Pick discriminants D in sequence of increasing h(D). For each D check if and whether 4N can be written as:

This part can be verified using Cornacchia's algorithm. Once acceptable D and a have been discovered, calculate . Now if m has a prime factor q of size

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]

Complex multiplication method

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 and (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 , which has roots corresponding to the h(D) values. Note, that is the class polynomial. From complex multiplication theory, we know that 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 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:

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

or [1] [10] [12]

Discussion

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.

Example of Atkin–Morain ECPP

We construct an example to prove that is prime using the Atkin–Morain ECPP test. First proceed through the set of 13 possible discriminants, testing whether the Legendre Symbol , and if 4N can be written as .

For our example is chosen. This is because and also, using Cornacchia's algorithm, we know that and thus a = 25 and b = 1.

The next step is to calculate m. This is easily done as which yields Next we need to find a probable prime divisor of m, which was referred to as q. It must satisfy the condition that

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, , but is not necessarily prime, and check whether, for each which divides s

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 's are 11 and 13. First, it is clear that , and so we need only check the values of

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

Next we compute

and we know our elliptic curve is of the form:

,

where k is as described previously and c a non-square in . So we can begin with

which yields

Now, utilizing the point P = (6,6) on E it can be verified that

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

Complexity and running times

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

of prime inputs.

Conjecture

Let be the number of primes smaller than 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 that can be verified in . [14]

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

Conjecture 2

Suppose there exist positive constants and such that the amount of primes in the interval

is larger than

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

[13]

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

for some [3]

Primes of special form

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 where , n odd can be proven prime (or composite) using elliptic curves. Of course this will also provide a method for proving primality of Mersenne numbers, which correspond to the case where n = 1. The following method is drawn from the paper Primality Test for using Elliptic Curves, by Yu Tsumura. [16]

Group structure of E(FN)

We take E as our elliptic curve, where E is of the form for where is prime, and with odd.

Theorem 1. [7]
Theorem 2. or 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 in the cyclic group

First we will present the case where n is relatively small with respect to , and this will require one more theorem:

Theorem 4. Choose a and suppose
Then p is a prime if and only if there exists a Q = (x,y) on E, such that for i = 1, 2, ...,k  1 and where is a sequence with initial value .

The algorithm

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

(1) Choose such that , and find such that .

Take and .

Then is on .

Calculate . If then is composite, otherwise proceed to (2).

(2) Set as the sequence with initial value . Calculate for .

If for an , where then is composite. Otherwise, proceed to (3).

(3) If then is prime. Otherwise, is composite. This completes the test.

Justification of the algorithm

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

Thus, if N is prime, Q' has order divisible by , by Theorem 3, and therefore the order of Q' is d | n.

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

Now, if the algorithm concludes that N is prime, then that means 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]

Related Research Articles

<span class="mw-page-title-main">Modular arithmetic</span> Computation modulo a fixed integer

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the third-fastest known factoring method. The second-fastest is the multiple polynomial quadratic sieve, and the fastest is the general number field sieve. The Lenstra elliptic-curve factorization is named after Hendrik Lenstra.

The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.

<span class="mw-page-title-main">Trapdoor function</span> One-way cryptographic tool

In theoretical computer science and cryptography, a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction without special information, called the "trapdoor". Trapdoor functions are a special case of one-way functions and are widely used in public-key cryptography.

In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878 and subsequently proved by Derrick Henry Lehmer in 1930.

The AKS primality test is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in an article titled "PRIMES is in P". The algorithm was the first one which is able to determine in polynomial time, whether a given number is prime or composite and this without relying on mathematical conjectures such as the generalized Riemann hypothesis. The proof is also notable for not relying on the field of analysis. In 2006 the authors received both the Gödel Prize and Fulkerson Prize for their work.

In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography.

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.

The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic test to determine if a number is composite or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 1967 (see Theorem E in the paper). This test has been largely superseded by the Baillie–PSW primality test and the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem. The Solovay–Strassen test is essentially an Euler–Jacobi probable prime test.

KCDSA is a digital signature algorithm created by a team led by the Korea Internet & Security Agency (KISA). It is an ElGamal variant, similar to the Digital Signature Algorithm and GOST R 34.10-94. The standard algorithm is implemented over , but an elliptic curve variant (EC-KCDSA) is also specified.

In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms. Dedicated to the discrete logarithm in where is a prime, index calculus leads to a family of algorithms adapted to finite fields and to some families of elliptic curves. The algorithm collects relations among the discrete logarithms of small primes, computes them by a linear algebra procedure and finally expresses the desired discrete logarithm with respect to the discrete logarithms of small primes.

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:

Schoof's algorithm is an efficient algorithm to count points on elliptic curves over finite fields. The algorithm has applications in elliptic curve cryptography where it is important to know the number of points to judge the difficulty of solving the discrete logarithm problem in the group of points on an elliptic curve.

The Tonelli–Shanks algorithm is used in modular arithmetic to solve for r in a congruence of the form r2n, where p is a prime: that is, to find a square root of n modulo p.

In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test. "Succinct" usually means that the proof should be at most polynomially larger than the number of digits in the number itself.

The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem (GM) created in 1985 by Josh (Cohen) Benaloh. The main improvement of the Benaloh Cryptosystem over GM is that longer blocks of data can be encrypted at once, whereas in GM each bit is encrypted individually.

<span class="mw-page-title-main">Key encapsulation mechanism</span>

In cryptography, a key encapsulation mechanism, or KEM, is a public-key cryptosystem that allows a sender to generate a short secret key and transmit it to a receiver securely, in spite of eavesdropping and intercepting adversaries.

An important aspect in the study of elliptic curves is devising effective ways of counting points on the curve. There have been several approaches to do so, and the algorithms devised have proved to be useful tools in the study of various fields such as number theory, and more recently in cryptography and Digital Signature Authentication. While in number theory they have important consequences in the solving of Diophantine equations, with respect to cryptography, they enable us to make effective use of the difficulty of the discrete logarithm problem (DLP) for the group , of elliptic curves over a finite field , where q = pk and p is a prime. The DLP, as it has come to be known, is a widely used approach to public key cryptography, and the difficulty in solving this problem determines the level of security of the cryptosystem. This article covers algorithms to count points on elliptic curves over fields of large characteristic, in particular p > 3. For curves over fields of small characteristic more efficient algorithms based on p-adic methods exist.

In mathematics the division polynomials provide a way to calculate multiples of points on elliptic curves and to study the fields generated by torsion points. They play a central role in the study of counting points on elliptic curves in Schoof's algorithm.

References

  1. 1 2 3 Henri Cohen, Gerhard Frey, ed. (2006). Handbook of Elliptic and Hyperelliptic Curve Cryptography. Boca Raton: Chapman & Hall/CRC.
  2. Top, Jaap, Elliptic Curve Primality Proving, http://www.math.rug.nl/~top/atkin.pdf
  3. 1 2 3 Atkin, A. O. L.; Morain, F. (1993). "Elliptic Curves and Primality Proving". Mathematics of Computation. 61 (203): 29–68. doi: 10.2307/2152935 . JSTOR   2152935.
  4. Lenstra, A.K.; Lenstra, H.W. (1990). "Algorithms in Number Theory". Algorithms and Complexity (PDF). pp. 673–715. doi:10.1016/B978-0-444-88071-0.50017-5. ISBN   9780444880710.
  5. Caldwell, Chris. The Top Twenty: Elliptic Curve Primality Proof from the Prime Pages.
  6. 1 2 Samuel S. Wagstaff Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. pp. 187–188. ISBN   978-1-4704-1048-3.
  7. 1 2 Washington, Lawrence C., Elliptic Curves: Number Theory and Cryptography, Chapman & Hall/CRC, 2003
  8. 1 2 Koblitz, Neal, Introduction to Number Theory and Cryptography, 2nd Ed, Springer, 1994
  9. "Queen's University Canada" (PDF). Archived from the original (PDF) on 2016-03-04. Retrieved 2010-01-22.
  10. 1 2 Blake, I.; Seroussi, G.; Smart, N. (1999). Elliptic Curves in Cryptography. doi:10.1017/CBO9781107360211. ISBN   9780521653749.
  11. Lenstra, Hendrik W., Efficient Algorithms in Number Theory, https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf
  12. ECPP Comes Back algo.inria.fr
  13. 1 2 Morain, F. (1988). "Implementation of the Atkin-Goldwasser-Kilian primality testing algorithm" (PDF). S2CID   118191463.
  14. Goldwasser, Shafi, Kilian, Joe, Almost All Primes Can Be Quickly Certified, http://www.iai.uni-bonn.de/~adrian/ecpp/p316-goldwasser.pdf Archived 2011-07-18 at the Wayback Machine
  15. "The Largest Known prime by Year: A Brief History".
  16. 1 2 Tsumura, Yu (2009). "Primality tests for using elliptic curves". arXiv: 0912.5279v1 [math.NT].