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:
- Generate a random 'n'-bit number
- Set the high- and low-order bits to 1.
- Make sure it is not divisible by small primes $p\in[2,2000]$.
- 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++
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)?