Primality Certificate - Pratt Certificates

Pratt Certificates

The concept of primality certificates was historically introduced by the Pratt certificate, conceived in 1975 by Vaughan Pratt, who described its structure and proved it to have polynomial size and to be verifiable in polynomial time. It is based on the Lucas primality test, which is essentially the converse of Fermat's little theorem with an added condition to make it true:

Suppose we have an integer a such that:

• a is coprime to n;
• an −1 ≡ 1 (mod n)
• For every prime factor q of n −1, it is not the case that a(n −1)/q ≡ 1 (mod n).

Then, n is prime.

Given such an a (called a witness) and the prime factorization of n−1, it's simple to verify the above conditions quickly: we only need to do a linear number of modular exponentiations, since every integer has fewer prime factors than bits, and each of these can be done by exponentiation by squaring in O(log n) multiplications (see big-O notation). Even with grade-school integer multiplication, this is only O((log n)4) time; using the multiplication algorithm with best-known asymptotic running time, the Schönhage–Strassen algorithm, we can lower this to O((log n)3(log log n)(log log log n)) time, or using soft-O notation Õ((log n)3).

However, it is possible to trick a verifier into accepting a composite number by giving it a "prime factorization" of n−1 that includes composite numbers. For example, suppose we claim that n=85 is prime, supplying a=4 and n−1=6×14 as the "prime factorization". Then (using q=6 and q=14):

• 4 is coprime to 85
• 485−1 ≡ 1 (mod 85)
• 4(85−1)/6 ≡ 16 (mod 85), 4(85−1)/14 ≡ 16 (mod 85)

We would falsely conclude that 85 is prime. We don't want to just force the verifier to factor the number so a better way to avoid this issue is to give primality certificates for each of the prime factors of n−1 as well, which are just smaller instances of the original problem. We continue recursively in this manner until we reach a number known to be prime, such as 2. We end up with a tree of prime numbers, each associated with a witness a. For example, here is a complete Pratt certificate for the number 229:

• 229 (a=6, 229−1 = 22×3×19)
  • 2 (known prime)
  • 3 (a=2, 3−1 = 2)
    • 2 (known prime)
  • 19 (a=2, 19−1 = 2×32)
    • 2 (known prime)
    • 3 (a=2, 3−1 = 2)
      • 2 (known prime)

This proof tree can be shown to contain at most values other than 2 by a simple inductive proof (based on Theorem 2 of Pratt). The result holds for 3; in general, take p > 3 and let its children in the tree be p₁,...,p_k. By the inductive hypothesis the tree rooted at p_i contains at most values, so the entire tree contains at most:

since k ≥ 2 and p₁...p_k = p−1. Since each value has at most log n bits, this also demonstrates that the certificate has a size of O((log n)2) bits.

Since there are O(log n) values other than 2 and each requires at most one exponentiation to verify (and exponentiations dominate the 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.