Revision history [back]

A much faster method is to generate a random integer p, to try dividing both p and (p-1)/2 by the first 100000 primes (just generate a table with those primes, using any suitable method) and reject p as soon as it is found that either p or (p-1)/2 has a divisor. If this is successful, then use the Miller-Rabin test on p and on (p-2)/2, using the first 10 primes as witnesses.

This is much faster because most p value will be rejected quickly, while first finding a prime p is much work and this work is useless because most of the time you can quickly find that (p-1)/2 is NOT prime. Better evaluate p and (p-1)/2 together, not focusing on one of them while ignoring the other one for a long time.