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

an−1 = 1 mod n


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 ≤ an − 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 φ.