Comment by adrian_b

4 days ago

While LCGs are bad by themselves, they (together with Galois field counters, which have a large number of possible implementations, e.g. LFSRs, GFSRs, XorShift etc.) have some very desirable properties for a PRNG: known period, it is possible to make jumps through the sequence and it is possible to extract sub-sequences from it that are certain to not overlap, e.g. for a multithreaded simulation.

Because of this, the best non-cryptographic PRNGs are made from either a LCG or a GFC that ensures the properties mentioned above, together with a non-linear mixing function that scrambles the output, for much better statistical properties than a linear generator would have alone.

The good cryptographic RNGs have the same kind of structure, but where a one-way hash function or a block cipher function is used to scramble the output of a counter. The counter ensures in a simpler way the same properties as a LCG or GFC. A simple counter can be used here because the output mixing function is much more complex.