elliptic curve primality proving
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
,
elliptic curve In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...
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 en, Shafrira Goldwasser , name = Shafi Goldwasser , image = Shafi Goldwasser.JPG , caption = Shafi Goldwasser in 2010 , birth_place = New York City, New York, U.S. , birth_date = , death_date ...
and
Joe Kilian Joe or JOE may refer to: Arts Film and television * ''Joe'' (1970 film), starring Peter Boyle * ''Joe'' (2013 film), starring Nicolas Cage * ''Joe'' (TV series), a British TV series airing from 1966 to 1971 * ''Joe'', a 2002 Canadian animated ...
in 1986 and turned into an algorithm by
A. O. L. Atkin Arthur Oliver Lonsdale Atkin (31 July 1925 – 28 December 2008), who published under the name A. O. L. Atkin, was a British mathematician. As an undergraduate during World War II, Atkin worked at Bletchley Park cracking German codes. He receiv ...
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 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 wh ...
is a field that has been around since the time of
Fermat Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he i ...
, 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 In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer. The test uses a partial factorization of N - 1 to prove that an integer N is prime. It produces a prim ...
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 In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
, 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 The worst-case execution time (WCET) of a computational task is the maximum length of time the task could take to execute on a specific hardware platform. What it is used for Worst case execution time is typically used in reliable real-time sys ...
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 test 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 whet ...
s do, finding a
group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
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 Goldwasser ("Gold water from Gdańsk"), pol. Wódka Gdańska, with Goldwasser as the registered tradename, is a strong (40% ABV) root and herbal liqueur which was produced from 1598 to 2009 in Gdańsk. Production now takes place in Germany. Th ...
–Kilian–Morain certificate of primality by
recursion Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
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 Hasse's theorem on elliptic curves, also referred to as the Hasse bound, provides an estimate of the number of points on an elliptic curve over a finite field, bounding the value both above and below. If ''N'' is the number of points on the ellip ...
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 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 t ...
) 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 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 whet ...
, 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 In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves ...
, 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 In mathematics, complex multiplication (CM) is the theory of elliptic curves ''E'' that have an endomorphism ring larger than the integers. Put another way, it contains the theory of elliptic functions with extra symmetries, such as are visible wh ...
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 In mathematics, the discriminant of a polynomial is a quantity that depends on the coefficients and allows deducing some properties of the roots without computing them. More precisely, it is a polynomial function of the coefficients of the origi ...
, ''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 In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo an odd prime number ''p'': its value at a (nonzero) quadratic residue mod ''p'' is 1 and at a non-quadratic residu ...
). 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 In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation x^2+dy^2=m, where 1\le d and ''d'' and ''m'' are
. Once acceptable ''D'' and ''a'' have been discovered, calculate m = N + 1 - a. Now if ''m'' has a prime factor ''q'' of size : q>(N^+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.


Complex multiplication method

For completeness, we will provide an overview of
complex multiplication In mathematics, complex multiplication (CM) is the theory of elliptic curves ''E'' that have an endomorphism ring larger than the integers. Put another way, it contains the theory of elliptic functions with extra symmetries, such as are visible wh ...
, 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 \neq -3 and D \neq -4 (these cases are much more easily done). It is necessary to calculate the elliptic
j-invariant In mathematics, Felix Klein's -invariant or function, regarded as a function of a Complex analysis, complex variable , is a modular function of weight zero for defined on the upper half-plane of complex numbers. It is the unique such funct ...
s 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 H_D(X), which has roots corresponding to the ''h''(''D'') values. Note, that H_D(X) is the class polynomial. From complex multiplication theory, we know that 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 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: : y^2 = x^3 - 3kc^x + 2kc^,\text k = \frac, ''c'' is any
quadratic nonresidue In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that: :x^2\equiv q \pmod. Otherwise, ''q'' is called a quadratic no ...
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(\mathbb/N\mathbb), = N+1-a or , E(\mathbb/N\mathbb), = N+1+a


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 N = 167 is prime using the Atkin–Morain ECPP test. First proceed through the set of 13 possible discriminants, testing whether the Legendre Symbol (D/N) = 1, and if 4''N'' can be written as 4N = a^2 + , D, b^2. For our example D = -43 is chosen. This is because (D/N) = (-43/167) = 1 and also, using
Cornacchia's algorithm In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation x^2+dy^2=m, where 1\le d and ''d'' and ''m'' are
, we know that 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 m = N + 1 - a which yields 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 q>(N^+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. It states, that given our ''m'', we look for an ''s'' which divides ''m'', s>(N^+1)^2, but is not necessarily prime, and check whether, for each p_i which divides ''s'' : (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 p_i's are 11 and 13. First, it is clear that 143 >(167^+1)^2, and so we need only check the values of : (143/11)P = 13P \qquad \text \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 In mathematics, Felix Klein's -invariant or function, regarded as a function of a Complex analysis, complex variable , is a modular function of weight zero for defined on the upper half-plane of complex numbers. It is the unique such funct ...
: j \equiv -960^3 \pmod \equiv 107 \pmod. Next we compute :k = \frac \pmod \equiv 158 \pmod and we know our elliptic curve is of the form: : y^2 = x^3 + 3kc^2x + 2kc^3, where ''k'' is as described previously and ''c'' a non-square in \mathbb_. So we can begin with :\begin r &= 0\\ 3k &\equiv 140 \pmod \\ 2k &\equiv 149 \pmod \end which yields :E: y^2 = x^3 + 140x + 149 \pmod Now, utilizing the point ''P'' = (6,6) on ''E'' it can be verified that 143 P = P_\infty. 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 : 1 - O\left(2^\right) of prime inputs.


Conjecture

Let \pi(x) be the number of primes smaller than ''x'' : \exists c_1, c_2 > 0: \pi(x+\sqrt) - \pi(x) \ge \frac 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(k^2) that can be verified in O(k^4).Goldwasser, Shafi, Kilian, Joe, ''Almost All Primes Can Be Quickly Certified'', http://www.iai.uni-bonn.de/~adrian/ecpp/p316-goldwasser.pdf Now consider another conjecture, which will give us a bound on the total time of the algorithm.


Conjecture 2

Suppose there exist positive constants c_1 and c_2 such that the amount of primes in the interval : , x+\sqrt x \ge 2 is larger than c_1\sqrt(\log x)^ Then the Goldwasser Kilian algorithm proves the primality of ''N'' in an expected time of : O(\log^ n) For the Atkin–Morain algorithm, the running time stated is : O((\log N)^) for some \epsilon > 0


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 mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17 ...
. 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 N = 2^kn - 1 where k,n \in \Z, k \ge 2, ''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 2^kn - 1 using Elliptic Curves'', by Yu Tsumura.


Group structure of ''E''(FN)

We take ''E'' as our elliptic curve, where ''E'' is of the form y^2 = x^3 - mx for m \in \Z, m \not\equiv 0 \bmod, where p \equiv 3 \bmod is prime, and p+1 = 2^kn, with k \in \Z, k \ge 2, n odd. :Theorem 1. E(\mathbb_p) = p+1. :Theorem 2. E(\mathbb_p) \cong \Z_ or E(\mathbb_p) \cong \Z_2 \oplus \Z_ 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 2^k in the cyclic group E(\mathbb_p) \cong \Z_. First we will present the case where ''n'' is relatively small with respect to 2^k, and this will require one more theorem: :Theorem 4. Choose a \lambda > 1 and suppose :: n \le \frac \qquad \text \qquad \lambda\sqrt > \left (\sqrt + 1 \right )^2. :Then ''p'' is a prime if and only if there exists a ''Q'' = (''x'',''y'') on ''E'', such that \gcd = 1 for ''i'' = 1, 2, ...,''k'' − 1 and S_k \equiv 0\pmod, where S_i is a sequence with initial value S_0 = x.


The algorithm

We provide the following algorithm, which relies mainly on Theorems 3 and 4. To verify the primality of a given number N, perform the following steps: (1) Choose x \in \mathbb such that \left(\frac\right) = -1, and find y \in \mathbb, y \not\equiv 0 \pmod such that \left(\frac\right) = 1. Take m = \frac\mod N and m \not\equiv 0 \pmod. Then Q'=(x,y) is on E: y^2=x^3-mx. Calculate Q = nQ'. If Q \in E then N is composite, otherwise proceed to (2). (2) Set S_i as the sequence with initial value Q. Calculate S_i for i=1, 2, 3, ..., k-1. If \gcd()>1 for an i, where 1 \le i \le k-1 then N is composite. Otherwise, proceed to (3). (3) If S_k \equiv 0 \pmod then N is prime. Otherwise, N 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 : \left(\frac\right) = \left(\frac\right) = \left(\frac\right)\left(\frac\right) = -1\cdot 1=-1. Thus, if ''N'' is prime, ''Q has order divisible by 2^k, by Theorem 3, and therefore the order of ''Q is 2^kd ''d'' , ''n''. This means ''Q'' = ''nQ has order 2^k. Therefore, if (1) concludes that ''N'' is composite, it truly is composite. (2) and (3) check if ''Q'' has order 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 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.


References


External links


Elliptic Curves and Primality Proving
by Atkin and Morain. * *Chris Caldwell
"Primality Proving 4.2: Elliptic curves and the ECPP test"
at the
Prime Pages The PrimePages is a website about prime numbers maintained by Chris Caldwell at the University of Tennessee at Martin. The site maintains the list of the "5,000 largest known primes", selected smaller primes of special forms, and many "top twenty" ...
. *François Morain
"The ECPP home page"
(includes old ECPP software for some architectures). *Marcel Martin

(binary for Linux 64-bit)
PARI/GP
a computer algebra system with functions to create Atkin-Morain and Primo primality certificates
GMP-ECPP
a free ECPP implementation
LiDIA
a free
C++ C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
library for Linux with ECPP support
CM
another free library that contains an ECPP implementation {{DEFAULTSORT:Elliptic Curve Primality Testing Primality tests