Random number generator in mpz_millerrabin
Fri, 13 Dec 2002 02:02:12 -0800
> Strictly speaking the current mpz_probab_prime_p=20
> (miller-rabin) is quite broken.
> 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 =
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 =
This primitive M-R test can then be wrapped in however many calls to =
whatever fancy PRNG is desired.