recursively encode the proof of primality for q < n, continuing until we reach a known prime. This certificate has size O((log n)2) and can be verified in O((log n)4) time. Moreover, the algorithm that generates these certificates can be shown to be expected polynomial time for all but a small fraction of primes, and this fraction exponentially decreases with the size of the primes. Consequently, it's well-suited to generating certified large random primes, an application that is important in cryptography applications such as generating provably valid RSA keys. Pocklington Based Certificates Provable prime generation based on variants of Pocklington's theorem (see Pocklington primality test) can be efficient techniques for generating primes (cost is generally less than probabilistic generation) with the added benefit of built in primality certificates. While these may seem to be special primes, notice that every prime integer could be generated with a Pocklington based provable generation algorithm. Pocklington Primality Tests Let where where are distinct primes with an integer greater than zero and a witness such that: Then P is prime if one of the following holds: Pocklington Primality Certificate A Pocklington primality certificate consists of the prime P, a set primes dividing , each with their own Pocklington prime certificate or small enough to be a known prime, and a witness . The bits needed for this certificate (and order of computational cost) should range from approximately for version () to for version () A Small Example Let . Note that and , . Using the 'witness' 2, equation is satisfied and using and . For version , the certificate needs only . for version , the certificate needs only , but there's a bit more work to do: and Using fails: Using succeeds: , and is prime. Impact of "PRIMES is in P" "PRIMES is in P" was a breakthrough in theoretical computer science. This article, published by Manindra Agrawal, Nitin Saxena, and Neeraj Kayal in August 2002, proves that the famous problem of checking primality of a number can be solved deterministically in polynomial time. The authors received the 2006 Gödel Prize and 2006 Fulkerson Prize for this work. Because primality testing can now be done deterministically in polynomial time using the AKS primality test, a prime number could itself be considered a certificate of its own primality. This test runs in Õ((log n)6) time. In practice this method of verification is more