Probability problem with Pratt prime proofs

In the process of creating a Pratt certificate to prove that a number n is prime, you have to find a number a that seems kinda arbitrary. As we discussed here, a number n is prime if there exists a number a such that

a^n-1 = 1 mod n

and

a^(n-1)/p 1 mod n

for all primes p that divide n - 1. How do you find a? You try something and see if it works. If it doesn't, you try again.

How many values of a might you have to try? Could this take a long time?

You need to pick 2 a n - 2, and there are (n-1) values of a that will work. Here is Euler's totient function. So the probability of picking a value of a that will work is

p = (n-1) / (n - 3).

The number of attempts before success has a geometric distribution with parameter p, and an expected value of 1/p.

So about how big is p? There's a theorem that says that (n)/n is asymptotically bounded below by

exp(-) / log log n

where = 0.577... is the Euler-Mascheroni constant. So for a 50-digit number, for example, we would expect p to be somewhere around 0.12, which says we might have to try eight or nine values of a. This estimate may be a little pessimistic since we based it on a lower bound for .

The post Probability problem with Pratt prime proofs first appeared on John D. Cook.