Pratt certificate

A Pratt certificate for a given integer $n$ is a primality certificate in which the numbers allow verification of primality by using the converse of Fermat’s little theorem (or Lehmer’s theorem). Generating a Pratt certificate requires knowledge of the prime factorization of $n-1$ (the primes $p_i$). Then, one must find a witness $w$ such that $w^{n-1}\equiv 1modn$ but not

$$w^{\frac{n-1}{p_i}}\equiv 1modn$$

for any $i\le \omega (n-1)$ (with $\omega (x)$ being the number of distinct prime factors function). Pratt certificates typically include witnesses not just for $n$ but also for the prime factors of $n-1$.

Because a Pratt certificate requires the factorization of $n-1$, it is generally only used for small numbers, with “small” being roughly defined as being less than about a billion. We’ll use a much smaller number for our example, one for which it would actually be faster to just perform trial division: $n=127$. We then have to factor 126, which gives us 2, 3, 3, 7. Choosing our witness $w=12$, we then see that ${12}^{126}\equiv 1mod127$ but ${12}^{63}\equiv -1mod127$, ${12}^{42}\equiv 107mod127$ and ${12}^{18}\equiv 8mod127$. Most algorithms for the Pratt certificate generally hard-code 2 as a prime number, but provide certificates for the other primes in the factorization. For this example we won’t bother to give certificates for 3 and 7.