Re: Revising prandom_32 generator

["Hannes Frederic Sowa" <hannes@stressinduktion.org>]

Hi,

On Tue, Mar 26, 2019, at 12:10, George Spelvin wrote:
> I started on a project to correct all of the instances of
> "prandom_u32() % FOO" in the kernel (there are lots)
> to "prandom_u32_max(FOO)".

The conversation definitely makes sense.

Are you trying to fix the modulo biases? I think that prandom_u32_max also has bias, would that be worth fixing as well?

> [...]
>
> Thw ones that seem interesting to me are:
> - Chris Doty-Humphrey's sfc32.  This is a 96-bit chaotic generator
>   (meaning period *probably* long but not well defined) fed with
>   a 32-bit counter to ensure a minimum period.  It's extremely
>   fast, and the author is also the author of PractRand, so it's
>   well-tested.
> - Vigna and Bacman's xoshiro128**.  This is a 128-bit LFSR with some
>   output postprocessing.
> - (on 64-bit machines) xoroshiro128**, by the same authors.
>   This is only efficient on 64-bit machines, so it would need
>   a have a 32-bit backup.
> - Bob Jenkins' jsf (originally "flea").  128 bits, good mixing,
>   fully chaotic.  I prefer the safety of a guaranteed minimum
>   period, but this is well thought of.
> - A lag-3 mutiply-with-carry generator.  2^32 - 1736 is the largest
>   "safe prime" mutiplier.

I think tausworthe is not _trivially_ to predict, what about your proposed algorithms? I think it is a nice to have safety-net in case too much random numbers accidentally leaks (despite reseeding).

Thanks,
Hannes