Random number generator in mpz_millerrabin

Paul Leyland pleyland@microsoft.com
Fri, 13 Dec 2002 02:02:12 -0800


> Strictly speaking the current mpz_probab_prime_p=20
> (miller-rabin) is quite broken.

True.

> The miller-rabin test requires a uniform=20
> distribution of random bases to get the stated probability
> of an error as being less than 1/4 .

That's *worst case* probability.  Typical case probability is much much =
lower.
Sorry to keep drawing attention to this distinction but people really =
don't seem to understand it.
(Jason, I know you do understand the distinction but nonetheless you =
never seem to make it in your writings.)

> For generating cryptographic primes none of this strict=20
> mathematical accuracy=20
> is required , only speed matters , therefore a new fn , something like

Some of us, and I'd suggest a significant number, require speed even =
when not generating cryptographic primes.  Which leads me into a plea:

Please can we have a documented function which performs one MR test to a =
base specified as an argument.  It is up to the programmer to call it an =
appropriate number of times and to select the argument from an =
appropriate distribution.  The argument could be a uint or mpz_t for all =
I care.  There could even be two such functions, one for each argument =
type.

This primitive M-R test can then be wrapped in however many calls to =
whatever fancy PRNG is desired.


Paul