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_2x+g_3 (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=kq with k!=1, mC(x,y,g_2,g_3,p) is the identity on the curve, but kC(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 Wolfram Language task ProvablePrimeQ[n] in the Wolfram Language package PrimalityProving` 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

Explore with Wolfram|Alpha


Atkin, A. O. L. and Morain, F. "Elliptic Curves and Primality Proving." Math. Comput. 61, 29-68, 1993.Bressoud, D. M. Factorization and Primality 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.

Referenced on Wolfram|Alpha

Atkin-Goldwasser-Kilian-Morain Certificate

Cite this as:

Weisstein, Eric W. "Atkin-Goldwasser-Kilian-Morain Certificate." From MathWorld--A Wolfram Web Resource.

Subject classifications