In short, my question is:
What exactly do people mean when they say that "The more you apply the Rabin-Miller test to a number, the more certain you can be that the number you're testing is prime."?
To clarify what I'm asking, let's look at an example I was working through:
Testing if N = 78007 is prime or not (spoiler, it is).
Rabin-Miller procedure:
- Find N - 1 = 2K * M
In this case, 78007 - 1 = 21*39003, which means K = 1 and M = 39003
Pick an A, such that 2 <= A <= N-2. We pick A = 2.
Compute B0 = AM % N.
If B0 = 1 or B0 = (N-1), then N is prime (probably). If it's anything else, we stop and conclude that N is not prime.
Else, begin computing terms of Bi = (Bi-1)2 % N, and: If Bi = 1, N is not prime. If Bi = N - 1, N is prime (probably).
Now, for our running example:
B0 = 239003 % 78007 = 1.
Which means N is probably prime.
HERE IS MY QUESTION: What would I proceed to do next if I want to be more certain that N is prime?
Would I try steps 2 and 3 with different A's?
Or would I keep the same A and proceed with the Bi terms until one of the Bi's turns out to be equal to 1? In which case the test says that N is not prime? If I reach such a Bi term, would that mean N is definitely not prime, or the more i's it took to get there, the more likely it is that N is actually prime?
Since I read a statement that said "If you do the Rabin-Miller test about 20 times on a big-ish number, you can be pretty certain it's prime." What exactly did they mean?
Thanks everyone in advance for any answers that clears it up for me.
Side note: I came across this primality test while looking for ways to generate a random 4000-bit prime number as part of implementing the Diffie-Hellman key exchange. I have written my own custom Big Integer library in C which I will be implementing Diffie-Hellman in. I implemented the Sieve of Eratosthenes but it was so damn slow. People say this primality test is way faster and can lead to high enough certainy that a number is prime for said number to be used in encryption schemes. If anyone knows of a better way, please let me know. I am no expert in encryption, but I really love implementing stuff on my own, it teaches me a lot more than simply using existing libraries for everything.
I tried reading explanations on several websites and asked on programming discord servers, watched several youtube videos but nobody was able to clarify this particular question to me. It's still unclear to me what exactly it means to "do the test 20 times on a number to be more certain that said number is prime".