Random number generators

[Pedro Giffuni]

On 03/17/15 12:07, Steve Kargl wrote:
> On Tue, Mar 17, 2015 at 07:10:46AM -0500, Pedro Giffuni wrote:
>>> One big issue is saving internal state.  IIRC, MT requires 623-bit
>>> of internal state.  KISS requires 4 32-bit int.  Thus, if
>>> you want to reseed the generator, KISS requires far less effort.
>>>
>> Yes, the problem is the that libc requires a single 32 (or 31) bit seed.
>> Given that restriction, our existing generator is not bad. Enforcing
>> something better breaks the API and is not really practical to get
>> crypto-grade randomness for stuff like refreshing a slide in a
>> presentation anyways.
>>
>> The musl libc approach seemed reasonable but I haven?t looked at the
>> base random generator there (I?ve heard the glibc one is not good at all).
>>
> GM's kiss generator has a period of 2**123.  The manpage
> for random(3) claims a period of about 2**35.  The rand(3)
> manpage does not give a period, but I suspect it is well
> short of 2**123.

I just started to look at the original KISS. It appears to be a
combination of three different pseudo random generators. In
particular it uses

static unsigned long Q[4194304]

and seeds it with CNG+XS. I am tempted to just seed it with a
crypto random source instead of using an LCG. This is not for
libc, just for entertainment purposes though :).

> The code that follows my sig uses. a Lehmer LCG generator to
> provide the 4 seeds needed for kiss.  The Lehmer LCG takes a
> single 32 bit seed.  If reseed() is not called prior to calling
> kiss(), then a default set of seeds is used.  If the argument
> to reseed() is 0 or 1, then the default set of seeds is used.
> It should be straight forward to map reseed() to srand() and
> kiss() to rand().  Do note that range kiss() is (0,UINT_MAX],
> so one needs to subtract 1 to get [0,UINT_MAX-1) if 0 needs
> to be in the range.
>
> To use this code in preference to random(3) (and in violation of
> POSIX?), initstate() and setstate() would need to muck with the
> internal state of kiss().  This is certainly possible, but I
> don't do it below.
>

Interesting. I don't really want to break POSIX but we have
3 pseudo random generators: rand(), random() and rand48().
It would be really nice if we could change one to be
modern (and fast) although not crypto friendly.

FWIW, the Playstation 4 carries Mersenne Twister in their
credits along with FreeBSD's libc and kernel so someone
has a use for a faster pseudo-random generator and a
better period than those we carry in libc.

Pedro.