10.1 Elliptic curve primality proving (ECPP)

Elliptic curve primality proving (ECPP) is a powerful method for verifying if a number is prime. It uses elliptic curves over finite fields to construct a sequence of curves with specific properties, ultimately proving primality.

ECPP relies on the relationship between elliptic curve group orders and field primality. It's more reliable than probabilistic tests and can be faster than other deterministic methods for large numbers, making it valuable in cryptography and number theory.

Elliptic curve primality proving (ECPP)

• Probabilistic primality testing method based on elliptic curves over finite fields
• Proves primality of integers by constructing a sequence of elliptic curves with certain properties
• Relies on the relationship between the order of elliptic curve groups and the primality of the underlying field

Atkin-Goldwasser-Kilian-Morain certificates

• Primality certificates used in ECPP to prove an integer is prime
• Consist of a sequence of elliptic curves and isogenies between them
• Each curve has a number of points that is almost prime, differing from a prime by a small cofactor
• Isogenies connect the curves, preserving the prime order up to the cofactor

Elliptic curve method for factorization

• Algorithm for integer factorization using elliptic curves (ECM)
• Finds a non-trivial factor of a composite number by constructing random elliptic curves over the ring modulo the number
• Hopes to find a curve with smooth order, leading to a factor via the greatest common divisor (GCD)
• Can be used as a subroutine in ECPP to prove primality by ruling out small factors

Relationship between ECPP and ECM

• ECPP uses the failure of ECM to provide evidence of primality
• If ECM fails to find factors after sufficiently many attempts, the number is likely prime
• ECPP constructs a certificate of primality by linking curves via isogenies
• ECM is a Monte Carlo algorithm, while ECPP is a Las Vegas algorithm (always correct, but running time varies)

Proving primality vs proving compositeness

• Primality testing determines whether a number is prime or composite
• Proving compositeness is generally easier, as finding a non-trivial factor suffices
• Proving primality requires showing no non-trivial factors exist
• ECPP provides a deterministic proof of primality, while most other methods are probabilistic

Probabilistic primality tests

• Algorithms that determine primality with a certain probability of error
• Examples include Fermat, Miller-Rabin, and Solovay-Strassen tests
• Rely on properties that hold for all primes but are unlikely for composites
• Can be fooled by pseudoprimes, composites that pass the test
• Probability of error can be reduced by repeating the test with different parameters

Deterministic primality proofs

• Algorithms that prove primality with certainty, no probability of error
• Typically slower than probabilistic tests, but provide a certificate of primality
• Examples include ECPP, AKS test, and cyclotomic methods
• Often impractical for very large numbers due to computational complexity

Goldwasser-Kilian algorithm

• First ECPP algorithm, developed by Shafi Goldwasser and Joe Kilian in 1986
• Constructs a sequence of elliptic curves over finite fields of increasing size
• Each curve has an almost prime number of points, certified by a recursively constructed primality proof
• Isogenies connect the curves, preserving the prime order up to a small cofactor
• Final curve has a prime number of points equal to the input, proving its primality

Atkin-Morain improvements

• Enhancements to the Goldwasser-Kilian algorithm by A. O. L. Atkin and François Morain
• Use complex multiplication to construct curves with a known number of points
• Employ isogenies of degree $\ell$ to connect curves, reducing the recursion depth
• Implement fast polynomial arithmetic to speed up computations
• Lead to a more practical and efficient ECPP algorithm

Suyama parametrization

• Method for constructing elliptic curves with a known number of points
• Developed by Hiromi Suyama in 1985
• Parametrizes curves by a single integer, simplifying the search space
• Guarantees the curve order is divisible by 12, useful for ECPP
• Allows efficient generation of curves with a desired number of points

Choosing curves for ECPP

• Selecting suitable elliptic curves is crucial for the efficiency of ECPP
• Curves should have an almost prime number of points, with a small cofactor
• Complex multiplication constructions (such as Suyama parametrization) help find such curves
• Curves with special properties (e.g., Montgomery form) can speed up computations
• Balancing security (curve size) and performance is important for practical implementations

Checking isogenies in ECPP

• Verifying the correctness of isogenies is a key step in ECPP
• Isogenies must preserve the prime order of the curves up to the cofactor
• Explicit formulas for isogenies of small degree can be used for efficiency
• Vélu's formulas provide a general method for computing isogenies
• Checking isogenies ensures the primality proof is valid

Complexity analysis of ECPP

• ECPP has a polynomial-time complexity, but the degree is relatively high
• The Goldwasser-Kilian algorithm has a running time of $O((\log n)^{10+\varepsilon})$ for proving $n$ is prime
• Atkin-Morain improvements reduce the complexity to around $O((\log n)^{6+\varepsilon})$
• Heuristic arguments suggest the average-case complexity may be lower
• Practical implementations have subexponential running times for large inputs

ECPP vs other primality tests

• ECPP is deterministic, providing a proof of primality, unlike probabilistic tests
• It is slower than probabilistic methods (e.g., Miller-Rabin) for most inputs
• ECPP is more complex to implement than other primality tests
• For very large numbers, ECPP may be more efficient than the AKS test
• ECPP has better worst-case complexity than cyclotomic methods

Implementing ECPP

• Efficient implementation of ECPP requires careful optimization
• Key components include curve construction, isogeny computation, and polynomial arithmetic
• Libraries for elliptic curve cryptography (e.g., MIRACL, Crypto++) can be adapted for ECPP
• Parallel and distributed implementations can help tackle large inputs
• Specialized hardware (e.g., FPGAs) can significantly speed up ECPP

Applications of ECPP in cryptography

• ECPP is used to generate prime numbers for cryptographic purposes
• Elliptic curve cryptography (ECC) relies on the difficulty of the discrete logarithm problem in elliptic curve groups
• Generating prime-order curves is crucial for the security of ECC
• ECPP can be used to prove the primality of the curve order and the underlying field size
• Other applications include generating RSA primes and testing the primality of Mersenne numbers