Random number generator in mpz_millerrabin

[Gary Wong]

Hi,

In another discussion with Pedro Gimeno, the issue of the random number
generator used by mpz_millerrabin() came up.  He informed me that the
problem had been discussed before, but no conclusion had been made, so
I thought I would raise the question here:

 One thing I want to ask you about is the speed of the Mersenne Twister
 generator in the Miller-Rabin test (mpz/millerrabin.c).  In mpz_millerrabin(),
 there is a call to gmp_randinit_default (i.e. the Mersenne Twister init
 function), which is then used for only a handful of calls to mpz_urandom
 before the state is discarded again.  On my system, this means that a
 call to mpz_millerrabin() takes over 30ms, whereas 16 repititions on a
 128-bit prime take only 1ms if a weaker 128-bit LCG is used instead.
 Eliminating the WARM_UP procedure of the MT generator makes no significant
 difference.
 
 One of the initialisation functions for BBS uses repeated Miller-Rabin
 tests, and a large speed increase would result if mpz_millerrabin()
 could avoid initialising Mersenne Twister state on every call.  Do you
 think that mpz_millerrabin() could be changed to use a weaker RNG with
 cheaper setup costs, or to somehow keep the RNG state between calls to
 avoid the initialisation costs each time?

Cheers,
Gary.
-- 
   Gary Wong           gtw@gnu.org           http://www.cs.arizona.edu/~gary/