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