Maurer's algorithm

[Pedro Gimeno]

Niels Möller wrote:
> I'm considering implementing some variant of Maurer's algorithm to
> generate prime numbers for cryptographic purposes. [...]
> 
> Next, select a random r, and set n = 2 q r + 1 as a candidate prime, [...]
>
> As a base case, when k is small (HoAC suggests when k <= 20), chose a
> random number of the right size and do trial division using a list of
> primes < 2^10. (And when k < 10, one could consider random selection
> from the prime list, I guess).

Please keep in mind that GMP does not generate cryptographically secure
random numbers and currently doesn't support pluggable generators
either. It would be a bad idea to rely on any of GMP's random number
generation facilities for this purpose. Perhaps a callback function
could solve the problem, so that the user can make use of a good
external source of random numbers (e.g. using OpenSSL).

-- Pedro Gimeno