Pratt certificate

A Pratt certificateMathworldPlanetmath for a given integer n is a primality certificateMathworldPlanetmath 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 factorizationMathworldPlanetmath of n-1 (the primes pi). Then, one must find a witnessMathworldPlanetmath w such that wn-11modn but not


for any iω(n-1) (with ω(x) being the number of distinct prime factors function). Pratt certificates typically include witnesses not just for n but also for the prime factorsMathworldPlanetmath 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 divisionMathworldPlanetmath: n=127. We then have to factor 126, which gives us 2, 3, 3, 7. Choosing our witness w=12, we then see that 121261mod127 but 1263-1mod127, 1242107mod127 and 12188mod127. Most algorithmsMathworldPlanetmath for the Pratt certificate generally hard-code 2 as a prime numberMathworldPlanetmath, 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