Seeding in MT (was: Re: Random number generator in mpz_millerrabin)

[pggimeno@wanadoo.es]

Kevin Ryde wrote:

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

I'm still wondering why would somebody use a seed greater than 2^54
(at least in a generator not suitable for cryptography). A constraint
in the design of the seeding function was to use the maximum possible
seed space, but I don't think that that's necessary in the case of MT,
given the speed penalty that it's causing.

OTOH changing the seeding method only for low seeds will cause a
collision, i.e. two seeds generating the same sequence, with
probability > 0.9999999999...(many, many 9's). Even though it would be
very unlikely to hit one of these `collided seeds' by chance, I
consider it a deficiency and would prefer to simply reduce the seed
space, if that's acceptable.

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

But if the seeding method changes with N, the risk of collision
increases substantially unless the maximum N is not too big.

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

That depends strictly on the final seed space, which is still an open
question.

BTW, it should be worth mentioning in the manual that MT is not
suitable for cryptography.