running time), the total time is O((log n)3(log log n)(log log log n)), or Õ((log n)3), which is quite feasible for numbers in the range that computational number theorists usually work with. However, while useful in theory and easy to verify, actually generating a Pratt certificate for n requires factoring n − 1 and other potentially large numbers. This is simple for some special numbers such as Fermat primes, but currently much more difficult than simple primality testing for large primes of general form. Atkin–Goldwasser–Kilian–Morain certificates To address the problem of efficient certificate generation for larger numbers, in 1986 Shafi Goldwasser and Joe Kilian described a new type of certificate based on the theory of elliptic curves. This was in turn used by A. O. L. Atkin and François Morain as the basis for Atkin-Goldwasser-Kilian-Morain certificates, which are the type of certificates generated and verified by elliptic curve primality proving systems. Just as Pratt certificates are based on Lucas's theorem, Atkin–Goldwasser–Kilian–Morain certificates are based on the following theorem of Goldwasser and Kilian (lemma 2 of "Almost All Primes Can Be Quickly Certified"): Theorem: Suppose we are given: a positive integer n not divisible by 2 or 3; Mx, My, A, B in (the integers mod n) satisfying My2 = Mx3 + AMx + B and with 4A3 + 27B2 coprime to n; a prime . Then M = (Mx, My) is a non-identity point on the elliptic curve y2 = x3 + Ax + B. Let kM be M added to itself k times using standard elliptic-curve addition. Then, if qM is the identity element I, then n is prime. Technically, an elliptic curve can only be constructed over a field, and is only a field if n is prime, so we seem to be assuming the result we're trying to prove. The difficulty arises in the elliptic-curve addition algorithm, which takes inverses in the field that may not exist in . However, it can be shown (lemma 1 of "Almost All Primes Can Be Quickly Certified") that if we merely perform computations as though the curve were well-defined and do not at any point attempt to invert an element with no inverse, the result is still valid; if we do encounter an element with no inverse, this establishes that n is composite. To derive a certificate from this theorem, we first encode Mx, My, A, B, and q, then