Random numbers for Rabin-Miller primality tests

Question

I've implemented a Rabin-Miller primality test fuction following Wikipedia and the book Applied Cryptography. Now I'm using it for generating primes with a string seed. The book suggests the following for this:

1. Generate a random 'n'-bit number
2. Set the high- and low-order bits to 1.
3. Make sure it is not divisible by small primes $p\in[2,2000]$.
4. Perform a Rabin-Miller Test for some random $a$. Choose a small value of $a$ to make it go quicker. Do five tests (I'm doing 40 as a post suggested here, and instead of generating a random number, I increment by one and test again.

So, first I used a random generator with uniform distribution to generate $a$, but after reading this, I changed it to the standard C++ rand() with srand(time(0)) seed. It is faster, but I'm not sure if it is the best way. Using boost's Twister was slower, but gave a wider range of $a$. I have searched (maybe not with right keywords) but how does choice of $a$ influence the test?

Is it good if the range is pretty small compared to the size of the number I test (saying $a$ is 32 bits, and the number is 512 bits)? Will it increase the odds of a false positive (pseudo prime)?

Answer 1

The fundamental property of the Rabin-Miller primality test is that, if the value $N$ being tested is composite, then it will return "composite" at least 75% of the time. That is, if we define the function $RabinMiller( N, A )$ that runs the Rabin-Miller test against the number $N$, using $A$ as a witness, then for any composite $N$, $RabinMiller( N, A )$ will evaluate as "Composite" for more than 75% of the values of $A$ in the range $[2, N-1]$.

So, you question is "what happens if we don't chose $A$ uniformly from the range $[2, N-1]$; what happens if we chose $A$ from a much smaller range?

The answer to that is that nobody really knows; we know that at least 75% of the numbers in $[2, N-1]$ will reveal $N$ to be composite, however there are no proven results how they might be distributed (there is a proof if we assume an unproven conjecture within number theory, but until we get a proof of that conjecture, it doesn't count). It would appear to be reasonable to conjecture that they are, in fact, reasonably well distributed, however we don't know that.

Hence, if you select your value $A$ from a smaller range, then while you probably have a good test, you have just voided the probabilistic provability that Rabin-Miller gives you.

In addition, there is also this fact that works in your favor; the Rabin-Miller proof states that, for any fixed composite $N$, that at least 75% of the values $A$ will return "composite", however for a random composite $N$, then $A$ will return "composite" almost all the time. While there are certain composite $N$ where a random $A$ will have a $\approx 25$% chance of returning "probably prime", however those $N$ values are rather rare (significantly rarer than primes). What this means is that, in practice, Rabin-Miller works significantly better than the proof would suggest.

So, that's the bottom line? Well, if you're interested in retaining the provability aspect of Rabin-Miller, you rather have to select values from the full range (and it's not all that expensive when compared to running the Rabin-Miller test). On the other hand, if you just want something that is likely to work, selecting from a smaller range is, as far as we know, reasonable.

Answer 2

You could start with a test using an integer from a restricted range, if that's faster (Speed is the only reason you're considering a restricted range, right?), as an efficient way to weed out most composites, and if that succeeds perform the 40 tests using the full range.