Random number generator in mpz_millerrabin

[Jason Moxham]

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=
=2E
Also for a given N , repeated calls to mpz_probab_prime_p will use the sa=
me=20
bases each time , therefore you can not just add the reps count from each=
=20
call , but only take the maximum

eg using=20

mpz_probab_prime_p(N,10);

and then=20

mpz_probab_prime_p(N,5);

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 =
can=20
do much better if you want to generate random probable primes (of say 200=
=20
bits)

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=
=20
proof) then the probability of error is even less and all the powering in=
 the=20
miller-rabin test can be done much faster.



For generating cryptographic primes none of this strict mathematical accu=
racy=20
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=
ed=20
long probability)

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

The function would use the fastest random number function (whatever that =
may=20
be) to generate random numbers , these would then be sieved and trial div=
ided=20
to eliminate "easy" composites , and if "probability" is low we would cho=
ose=20
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

and

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=
=20
obsolete(just retained for backwards compatibility only). Its inaccurate =
,=20
and when this doesn't matter , its an order of magnitude slower than it c=
ould=20
be.

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

Jason