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=
=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