Problem with gmp_randinit_set

[Marco Bodrato]

Ciao,

Il Mar, 21 Febbraio 2017 5:14 pm, Pedro Gimeno ha scritto:
> Marco Bodrato wrote, On 2017-02-21 15:21:

>> value and (2^n-k-value) will be mangled to the same seed...
>> <snipped additional problem>
>
> Well, these are more bugs then.

> As I said it's all or nothing. Either compatibility is kept, or the
> whole thing is changed to a better and faster seeding function.

Maybe a compromise is possible.

I attach a patch, it applies to the current development code... it is not
meant to be simply a proposed replacement for the seeding function, it's a
proof of concept.

It extends the seeding xxtea_randseed_mt() function proposed by Pedro
Gimeno taking into account also the highest bit, in such a way that:
 - every seed in the range 0 <= seed < 2^19936 generate a different
random sequence;
 - every seed in the range 2^19936 <= seed < 2^19937 generate a different
random sequence;
 - there are exactly two seeds 0 <= seed1 < 2^19936 <= seed2 < 2^19937
that generate the same sequence. (It's easy to compute both, if needed)

I recall that with the current function there are (literally) dozens of
seeds giving the same sequence in the range 0 <= seed < 2^19937, with the
proposed one there is a single couple, for a grand total of exactly
2^19937-1 different sequences.

It defines a legacy_randseed_mt() function that manipulates the given seed
to obtain the value that must be passed to the xxtea_randseed_mt()
function to generate exactly the same sequence that the old (current)
randseed_mt() function generates.

The attached patch uses legacy_randseed_mt. So that nothing changes.

Of course the real proposal is to _change_ the randseed function, and to
give (as an internal extra function, or as a source code to be inserted in
programs needing it) a function that allows anyone to obtain the same
sequences GMP generated till today.

Comments are welcome,
mb

PS: there is at least one program requiring that our random functions
generate exactly the expected numbers for some given seeds:
tests/mpz/t-gcd.c

-- 
http://bodrato.it/papers/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: rand.patch
Type: text/x-patch
Size: 4299 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-bugs/attachments/20170302/1eb74d72/attachment.bin>