LCG (Linear Congruential Generator)

The simplest PRNG:

next = (a * state + c) mod m

Where a, c, m are constants. Common values (numerical recipes):

• a = 1664525, c = 1013904223, m = 2^32

This is C's rand() for many implementations. Output is the upper bits of state.

LCGs are FAST and have decent statistical properties for non-crypto use. But:

• LOW-bit periodicity: low bits cycle quickly. rand() % 2 flips perfectly!
• Plane structure: triples (x_i, x_{i+1}, x_{i+2}) lie on a small number of hyperplanes (Marsaglia, 1968).
• Predictable: ~50 outputs reveal a, c, m.

Even Mersenne Twister (which LCG is far worse than) is broken from observation.

Modern non-crypto PRNGs:

• xoshiro256++: 256-bit state, faster than MT, better statistics
• PCG: 64-bit state, very fast, hard-to-predict for casual use

Use these for SIMULATIONS. Never for crypto.

For crypto, the algorithms must be UNPREDICTABLE — given any number of outputs, the next output looks uniform.