ECPP

ECPP
Name	ECPP
Full name	Elliptic Curve Primality Proving
Type	Primality-proving algorithm
Introduced	1987
Inventors	Atkin–Morain variants
Key people	A. O. L. Atkin, François Morain, John Coates, Andrew Wiles
Related	Elliptic curve cryptography, Primality test, AKS primality test, Miller–Rabin test, Lucas–Lehmer test

ECPP is a deterministic, number-theoretic algorithm for certifying that a given integer is prime by constructing and verifying properties of elliptic curves with complex multiplication or via general elliptic curve methods. It produces concise certificates that can be checked substantially faster than generating them, and it has been used to prove primality of very large integers in computational number theory and cryptography. ECPP connects classical topics in algebraic number theory, modular functions, and computational arithmetic geometry.

Overview

ECPP rests on deep results about Elliptic curve endomorphism rings, Complex multiplication, and point-counting on elliptic curves over finite fields such as Fermat primes and integers related to Mersenne primes proofs. The algorithm constructs an elliptic curve E over Z/nZ together with a point P and an integer m such that the group order #E(Z/nZ) factors in a way that forces n to be prime if certain congruences and divisibility conditions hold; this approach leverages connections to Heegner numbers, Hilbert class polynomials, and the theory of Algebraic number theory in the style of explicit Deuring’s theorem-type correspondences. ECPP’s certificate typically contains a sequence of smaller primes, curve parameters, and group orders that form a chain terminating at small, trivially verifiable primes such as 2 or 3.

History and Development

The conceptual roots trace to work on elliptic curves and Complex multiplication in the mid-20th century, influenced by figures like Heegner, Stark, and Baker. The explicit algorithmic form often cited is the Atkin–Morain method developed in the late 1980s by A. O. L. Atkin and François Morain, who produced practical ECPP implementations and used them to certify large primes. Subsequent advances involved improvements in computing Hilbert class polynomials by researchers connected to Coxeter-style explicit class field theory and computational advances by teams including Peter L. Montgomery, Robert Gerbicz, and Tomás Oliveira e Silva. ECPP’s evolution paralleled progress in fast integer arithmetic like the Schönhage–Strassen algorithm and fast modular arithmetic libraries, enabling record-breaking primality certificates for numbers arising in projects associated with Great Internet Mersenne Prime Search, PrimeGrid, and independent mathematical computations.

Algorithm and Techniques

At its core, ECPP constructs elliptic curves with prescribed complex multiplication by an imaginary quadratic order of discriminant D linked to a target prime candidate n. The steps involve computing or selecting a suitable discriminant D, obtaining associated class invariants such as values of j-invariant via Hilbert class polynomial roots modulo n, defining curve models (e.g., Montgomery or short Weierstrass forms), and performing point-counting or using known group orders derived from the CM theory. Certificates record curve coefficients, points, and orders so verifiers execute scalar multiplications and gcd checks akin to protocols used in Pocklington’s theorem-style criteria but adapted to elliptic curves. Practical ECPP variants incorporate fast techniques from Schoof’s algorithm and improvements like the use of modular polynomials, optimized point arithmetic on curves over composite moduli, and heuristics for selecting small class numbers from tables associated with Heegner numbers and imaginary quadratic fields.

Applications and Use Cases

ECPP is used to produce unambiguous primality certificates for integers used in research and cryptographic parameter validation such as keys in RSA, primes for Diffie–Hellman key exchange, and primes underlying Elliptic curve cryptography curve generation. It has been applied in projects verifying large primes discovered by participants in PrimeGrid and to confirm mathematical results dependent on primality of specific constants appearing in tables maintained by organizations like the On-Line Encyclopedia of Integer Sequences and in computational proofs tied to results by mathematicians such as Adam Parry or experimental computations in analytic number theory related to Riemann Hypothesis-adjacent computations. ECPP’s short certificates facilitate archival and peer-reviewed publication of primality claims in journals and database entries maintained by institutions such as American Mathematical Society-related repositories.

Performance and Complexity

The heuristic running time of state-of-the-art ECPP implementations is often modeled as approximately L_n[1/2, c] for some constant c in the subexponential framework, making it practically faster than general deterministic tests like the AKS primality test for numbers of sizes encountered in practice. Worst-case theoretical bounds are subtler, relying on unproven heuristics about distribution of suitable discriminants and class numbers tied to Generalized Riemann Hypothesis-style assumptions; nevertheless, empirical performance benefits from fast integer multiplication and optimized elliptic-curve arithmetic pioneered by implementers such as Karatsuba-style developers and contributors to libraries like GNU Multiple Precision Arithmetic Library. Certificate verification typically involves a small polynomial number of modular multiplications and elliptic scalar multiplications, often many orders of magnitude cheaper than the generation step.

Implementations and Software

Notable implementations include the original programs by Atkin and Morain, public-domain packages integrated into systems such as PARI/GP and libraries collaborating with GMP and MPFR. Other widely used software includes standalone ECPP tools written by computational number theorists like François Morain collaborators, and integrated features in projects such as Primality proving libraries distributed with SageMath and specialized modules in Mathematica-adjacent packages. Community-driven projects and repositories maintained on platforms frequented by researchers in computational algebraic number theory provide source code, test suites, and example certificates used by practitioners in universities and research institutions including Université de Bordeaux, CNRS, and various mathematics departments.

Category:Primality tests