A Pratt certificate for a given integer 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 (the primes ). Then, one must find a witness such that but not
Because a Pratt certificate requires the factorization of , 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: . We then have to factor 126, which gives us 2, 3, 3, 7. Choosing our witness , we then see that but , and . 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.
|Date of creation||2013-03-22 18:53:06|
|Last modified on||2013-03-22 18:53:06|
|Last modified by||PrimeFan (13766)|