Atkin-Goldwasser-Kilian-Morain Certificate

A recursive Primality Certificate for a Prime $p$. The certificate consists of a list of

1. A point on an Elliptic Curve $C$

$$y^2 = x^3 + g_2 x + g_3 \ ({\rm mod\ } p)$$

for some numbers $g_2$ and $g_3$.

2. A Prime $q$ with $q > (p^{1/4} + 1)^2$, such that for some other number $k$ and $m = k q$ with $k\not=1$, $mC(x,y,g_2,g_3,p)$ is the identity on the curve, but $k C(x,y,g_2,g_3,p)$ is not the identity. This guarantees Primality of $p$ by a theorem of Goldwasser and Kilian (1986).

3. Each $q$ has its recursive certificate following it. So if the smallest $q$ is known to be Prime, all the numbers are certified Prime up the chain.

A Pratt Certificate is quicker to generate for small numbers. The Mathematica ${}^{\scriptstyle\circledRsymbol}$ (Wolfram Research, Champaign, IL) task ProvablePrime[n] therefore generates an Atkin-Goldwasser-Kilian-Morain certificate only for numbers above a certain limit ($10^{10}$ by default), and a Pratt Certificate for smaller numbers.

See also Elliptic Curve Primality Proving, Elliptic Pseudoprime, Pratt Certificate, Primality Certificate, Witness

References

Atkin, A. O. L. and Morain, F. ``Elliptic Curves and Primality Proving.'' Math. Comput. 61, 29-68, 1993.

Bressoud, D. M. Factorization and Prime Testing. New York: Springer-Verlag, 1989.

Goldwasser, S. and Kilian, J. ``Almost All Primes Can Be Quickly Certified.'' Proc. 18th STOC. pp. 316-329, 1986.

Morain, F. ``Implementation of the Atkin-Goldwasser-Kilian Primality Testing Algorithm.'' Rapport de Recherche 911, INRIA, Octobre 1988.

Schoof, R. ``Elliptic Curves over Finite Fields and the Computation of Square Roots mod $p$.'' Math. Comput. 44, 483-494, 1985.

Wunderlich, M. C. ``A Performance Analysis of a Simple Prime-Testing Algorithm.'' Math. Comput. 40, 709-714, 1983.