Random number generator in mpz_millerrabin

Kevin Ryde user42@zip.com.au
Sat, 21 Dec 2002 07:49:04 +1000

pggimeno@wanadoo.es writes:
> the other is that mpz_millerrabin should know about
> the structure of MT's context.

That's ok since it's internal, if no better option presents itself.

> Another `quick and dirty' possibility is to make mpz_millerrabin use
> gmp_randinit_lc_2exp instead of gmp_randinit_default.

If that'd be random enough that'd be ok.

We end up with a set of bases depending only on N, so maybe almost any
non-repeating sequence would be good enough.

> Initialization with a lower seed space (say seeds in range 0 to
> 2^54-1) would be possible and perhaps desirable; some good and fast
> 32-bit PRNGs can be used. A drawback is that only a subset of the
> possible buffer values would then be available, and it would be
> harder to give guarantees that no two different seeds produce the
> same sequence.

Existing programs without terribly special requirements might be doing
something as simple as passing the output of "time()".  For instance
the GMP test programs :-).  So there might be some value in optimizing
for small seeds.

Perhaps if the user passes a seed consisting of N bits then it could
be considered a selection from an N bit space, and applied to the
buffer accordingly, by some means.

In any case we still need to try to give some advice in the manual
about what sort of seed to pass and broadly how it'll be interpreted.