# 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.

Title | Pratt certificate |
---|---|

Canonical name | PrattCertificate |

Date of creation | 2013-03-22 18:53:06 |

Last modified on | 2013-03-22 18:53:06 |

Owner | PrimeFan (13766) |

Last modified by | PrimeFan (13766) |

Numerical id | 4 |

Author | PrimeFan (13766) |

Entry type | Definition |

Classification | msc 11A41 |