Problem with gmp_randinit_set
Marco Bodrato
bodrato at mail.dm.unipi.it
Tue Feb 21 14:21:09 UTC 2017
Ciao,
Il Sab, 18 Febbraio 2017 12:42 am, Pedro Gimeno ha scritto:
> Yes. Only seeds up to 2^19937-20028 inclusive are guaranteed to generate
> different sequences, though, and with the new seeding function, only up to
> 2^19936-1. I don't think it'd be a big deal to cut it out to 2^19936-1
I'm looking more carefully at the code... and I doubt we are really giving
different sequences for all seeding-values up to 2^19937-20028.
We mangle the given value to obtain the seed with:
(value^e) mod (2^n-k) for e=1074888996, n=19937 and k=20023,
right?
Problem: e is even!
value and (2^n-k-value) will be mangled to the same seed...
Moreover, gcd(e, 2^n-k-1) = 12. I expect to find dozens of values giving
the same result after the exponentiation. So that we currently have only
2^19937-20028 different sequences that can be selected by a seed. If we
can obtain 2^19936-1, it's not a cut, it's an improvement!
Of course we can change the exponent, with a new one, co-prime with the
Euler phi of 2^n-k... but this is an incompatible change.
I'm leaning more and more towards the complete change of the seeding
function.
> now. Seeds bigger would generate different results, potentially breaking
> compatibility if these are used, but I don't think there's a big chance of
> that happening.
If we change the function, the sequences will be changed for any value,
right? It's not only an issue affecting "bigger seeds"...
Best regards,
m
--
http://bodrato.it/papers/
More information about the gmp-bugs
mailing list