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. 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 formula_1 in order to prove that formula_2 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 formula_4. This  exponent may be decreased to formula_5 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 formula_6 is prime. For ECPP the group is an elliptic curve over a finite set of quadratic forms such that formula_7 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. As of March 2022, the largest prime that has been proved with ECPP method is the repunit "R"(49081), which has 49,081 digits. The certification by Paul Underwood took 20 months using Marcel Martin's Primo software. Proposition. The elliptic curve primality tests are based on criteria analogous to the Pocklington criterion, on which that test is based, where the group formula_8 is replaced by formula_9 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 formula_10 Consider "E" over formula_11 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 formula_12 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 formula_13 that divides "N". Define formula_14 as the elliptic curve defined by the same equation as "E" but evaluated modulo "p" rather than modulo "N". Define formula_15 as the order of the group formula_14. By Hasse's theorem on elliptic curves we know and thus formula_18 and there exists an integer "u" with the property that Let formula_20 be the point "P" evaluated modulo "p". Thus, on formula_14 we have by (1), as formula_23 is calculated using the same method as "mP , except modulo p" rather than modulo "N" (and formula_24). 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: 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 Now "P" = ("x","y") is a point on "E", where we have that "E" is defined by formula_27. 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, 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 formula_28 where formula_29 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 formula_30 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 formula_31 and formula_32 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. 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 formula_33, 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 formula_34, 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 formula_36 with complex multiplication (described in detail below), and the number of points is given by: The test. Pick discriminants "D" in sequence of increasing "h"("D"). For each "D" check if formula_38 and whether 4"N" can be written as: This part can be verified using Cornacchia's algorithm. Once acceptable "D" and "a" have been discovered, calculate formula_43. 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. 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 formula_45 and formula_46 (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 formula_47, which has roots corresponding to the "h"("D") values. Note, that formula_47 is the class polynomial. From complex multiplication theory, we know that formula_47 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 formula_47 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 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 formula_54 is prime using the Atkin–Morain ECPP test. First proceed through the set of 13 possible discriminants, testing whether the Legendre Symbol formula_55, and if 4"N" can be written as formula_56. For our example formula_57 is chosen. This is because formula_58 and also, using Cornacchia's  algorithm, we know that formula_59 and thus "a" = 25 and "b" = 1. The next step is to calculate "m". This is easily done as formula_43 which yields formula_61 Next we need to find a probable prime divisor of "m", which was referred to as "q". It must satisfy the condition that formula_62 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. It states, that given our "m", we look for an "s" which divides "m", formula_63, but is not necessarily prime, and check whether, for each formula_64 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 formula_64's are 11 and 13. First, it is clear that formula_67, 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 formula_72. So we can begin with which yields Now, utilizing the point "P" = (6,6) on "E" it can be verified that formula_75 It is simple to check that 13(6, 6) = (12, 65) and 11"P" = (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 formula_77 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 formula_79 that can be verified in formula_80. Now consider another conjecture, which will give us a bound on the total  time of the algorithm. Conjecture 2. Suppose there exist positive constants formula_81 and formula_82 such that the amount of primes in the interval Then the Goldwasser Kilian algorithm proves the primality of "N" in an expected time of For the Atkin–Morain algorithm, the running time stated is 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 number . 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 formula_88 where formula_89, "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. There is a method in place for testing this form of number without elliptic curves (with a limitation on the size of k ) known as the Lucas–Lehmer–Riesel test. The following method is drawn from the paper "Primality Test for formula_90 using Elliptic Curves", by Yu Tsumura. Group structure of "E"(F). We take "E" as our elliptic curve, where "E" is of the form formula_91 for formula_92 where formula_93 is prime, and formula_94 with formula_95 odd. First we will present the case where "n" is relatively small with respect to formula_99, and this will require one more theorem: The algorithm. We provide the following algorithm, which relies mainly on Theorems 3 and 4. To verify the primality of a given number formula_2 , perform the following steps: (1) Choose formula_109 such that formula_110, and find formula_111 such that formula_112. Take formula_113 and formula_114. Then formula_115 is on formula_116. Calculate formula_117. If formula_118 then formula_2 is composite, otherwise proceed to (2). (2) Set formula_106 as the sequence with initial value formula_121. Calculate formula_106 for formula_123formula_124. If formula_125 for an formula_126, where formula_127 then formula_2 is composite. Otherwise, proceed to (3). (3) If formula_129 then formula_2 is prime. Otherwise, formula_2 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 formula_99, by Theorem 3, and therefore the order of "Q"' is formula_134 "d" | "n". This means "Q" = "nQ"' has order formula_99. Therefore, if (1) concludes that "N" is composite, it truly is composite. (2) and (3) check if "Q" has order formula_99. Thus, if (2) or (3) conclude "N" is composite, it is composite. Now, if the algorithm concludes that "N" is prime, then that means formula_137 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.