Elliptic Curve Primality Proving is a method based on elliptic curves to prove the primality of a number. It is a general-purpose algorithm: It does not depend on the number being a special form. ECPP runs in time (see Lenstra's paper below) In mathematics, elliptic curves are defined by certain cubic (the superscript exponent is three, a. ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ...

for some ε > 0. This exponent may be decreased to 4 + ε by heuristic arguments. This exponent is less than that of the AKS method. ECPP works the same way as most other primality tests do, finding a group 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. Look up Heuristic in Wiktionary, the free dictionary. ... The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by three Indian scientists named Manindra Agrawal, Neeraj Kayal and Nitin Saxena on August 6, 2002 in a paper titled PRIMES is in P. The... A primality test is an algorithm for determining whether an input number is prime. ... In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ...

ECPP generates an Atkin-Goldwasser-Kilian-Morain certificate of primality by divide and conquer and then attempts to verify the certificate. The step that takes the most cpu time is the certificate generation as factoring over a class field must be performed. The certificate can be verified quickly, allowing a check of operation to take very little time. In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. ... In computer science, divide and conquer (D&C) is an important algorithm design paradigm. ... In mathematics, class field theory is a major branch of algebraic number theory. ...

External link

• Elliptic Curves and Primality Proving Atkin and Morain.
• Lenstra, Jr., A. K. and Lenstra, Jr., H. W., Algorithms in number theory. In "Handbook of Theoretical Computer Science, Vol A: Algorithms and Complexity," The MIT Press, Amsterdam and New York, pp. 673-715, 1990.