nsajko / go-prng-test Goto Github PK

The PRNG of the math/rand package is implemented by the rngSource struct, which has the Seed method, whose beginning contains a surprise:

	seed = seed % int32max
	if seed < 0 {
		seed += int32max
	}
	if seed == 0 {
		seed = 89482311
	}

See https://tip.golang.org/src/math/rand/rng.go

(The constant int32max defined as (1 << 31) - 1 in the same file.)

The Seed function throws away entropy, even though even the full 64 bits (seed is of type int64) wouldn't be enough to fill the huge 4856-byte state of the PRNG! This is actually partially documented, at least for the default Source, for which the documentation says:

Seed values that have the same remainder when divided by 2³¹-1 generate the same pseudo-random sequence.

This blog post prompted me to do some tests to check how the small amount (relative to state size) of input entropy affects certain qualities of the rngSource PRNG.

I'm not an expert (far from it), so it's possible I'm abusing some terminology myself. I'll give this definition though, it might help someone.

The pseudo-random stream/sequence, mentioned in several places in this repo, refers to the ordered collection of number values generated by a PRNG (pseudo-random number generator). The "pseudo" is because these are deterministic algorithms, as opposed to true randomness.

Sometimes I refer to positions within the stream, position 0 is the first generated value, position 1 is the second one, etc.

See this for the results regarding generated values that belong to a small predetermined range.

See this for the results of a test that concetrates on math/rand.Rand.Int63, and the first position of its pseudo-random sequences, counting how many distinct generated values exist.

Note that the experimental code in golang.org/x/exp/rand, currently the intended replacement for math/rand in Go 2, (apart from implementing a better PRNG algorithm) has the method UnmarshalBinary (on PCGSource), which kind of prevents similar issues there, as it makes it possible to initialize the entire 128-bit state of the PRNG. But PCGSource also has a Seed method, which only takes a single uint64 input value as the seed, and the Source interface in golang.org/x/exp/rand only includes the Seed method. I hope the Source interface gets a redesign before any breaking changes to Go are made, maybe the API could be based on a sponge/duplex construction (which would be quite flexible, enable reseeding, but would perhaps be a better fit to a PRNG that actually is a sponge/duplex, unlike the simpler PCG family).