Random number generator in mpz_millerrabin

Jason Moxham J.L.Moxham@maths.soton.ac.uk
Fri, 13 Dec 2002 04:28:15 +0000

Strictly speaking the current mpz_probab_prime_p (miller-rabin) is quite=20
broken . The miller-rabin test requires a uniform distribution of random=20
bases to get the stated probability of an error as being less than 1/4 .

In gmp-4.1.1 mpz_urandomb is used rather than mpz_urandomm which results =
in a=20
non-uniform distribution of bases , this is fixed in the current snapshot=
Also for a given N , repeated calls to mpz_probab_prime_p will use the sa=
bases each time , therefore you can not just add the reps count from each=
call , but only take the maximum

eg using=20


and then=20


would give a probability of error of 1 in 4^10  not 1 in 4^15

For cryptographic uses the above is true , but due to another theorem we =
do much better if you want to generate random probable primes (of say 200=

only a few reps (say 1 to 5) are neccessary for a fantastically low=20
probability of error , and if your willing to use conjecture (rather than=
proof) then the probability of error is even less and all the powering in=
miller-rabin test can be done much faster.

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

void mpz_generate_crypto_primes(mpz_t *prime_array , unsigned long=20
prime_array_size , gmp_randstate_t rndstate , unsigned long bits , unsign=
long probability)

which fills the mpz_t array with "prime_array_size" random probable prime=
each of "bits" bits , where "probability" describes how secure the primes=
should be .

The function would use the fastest random number function (whatever that =
be) to generate random numbers , these would then be sieved and trial div=
to eliminate "easy" composites , and if "probability" is low we would cho=
one base , otherwise choose many bases , and use multiple simultaneous=20
powering to identitfy those that are probably prime.

and two other functions

int mpz_miller_rabin(mpz_t N,gmp_randstate_t rndstate,int reps)

for those who want a real random miller-rabin test


int mpz_probable_prime_p(mpz_t N,gmp_randstate_t rndstate,int prob)

for those who want something better

Basically the current mpz_probab_prime_p is a mistake and should declared=
obsolete(just retained for backwards compatibility only). Its inaccurate =
and when this doesn't matter , its an order of magnitude slower than it c=

I have replacements for the above (I haven't writen the crypto one yet) ,=
just need a bit of a clean up.