Linear Congruential Generators

Pseudo-random number generators are deterministic algorithms that produce sequences which look random, even though every output is completely determined by the internal state. One of the simplest and most important examples is the linear congruential generator, or LCG.

The basic idea

An LCG keeps a single integer state x_n and updates it with a fixed arithmetic rule:

x_(n+1) = (a * x_n + c) mod m

Here:

• x_n is the current state
• a is the multiplier
• c is the increment
• m is the modulus

Each time you apply the recurrence, you get a new state. That new state is then used as the next output, or as the source of the next output.

This is the core intuition behind using an LCG as a PRG:

1. Start from a seed.
2. Repeatedly apply a deterministic update rule.
3. Treat the resulting values as a random-looking sequence.

If you do not know the seed, the outputs can appear irregular. But the generator is not actually random. It is just following a mathematical rule.

Why modular arithmetic is used

Without the mod m, the state would grow without bound. The modulus keeps the state inside a fixed range:

0 <= x_n < m

This makes the generator efficient and easy to implement. It also means the generator has a finite state space, so eventually the sequence must repeat. A well-chosen LCG tries to make that repetition happen as late as possible.

Park-Miller

The Park-Miller generator is a famous special case of an LCG. It is defined by:

x_(n+1) = (16807 * x_n) mod (2^31 - 1)

So its constants are:

• a = 16807
• c = 0
• m = 2147483647

This is sometimes called the "minimal standard" generator. Historically, it was popular because it is easy to implement, fast, and mathematically clean.

Unlike the general LCG formula, Park-Miller uses no increment. The next state is produced only by multiplying the current state by a fixed constant and reducing modulo a large prime.

Why it looks random

A good PRG does not need to be truly random. It only needs to produce outputs that are difficult to distinguish from random for the intended use.

For a simple generator like Park-Miller, the combination of multiplication and modular reduction causes the state to move around a large set of values in a way that can look noisy to a casual observer. Different seeds produce different sequences, and the period can be long enough for small applications.

That is why LCGs were historically used in simulations, games, and older libraries.

Xorshift PRGs

What is a Xorshift generator?

The Xorshift family is a class of pseudorandom number generators introduced by George Marsaglia. These generators update their internal state using only:

• XOR
• bit shifts
• sometimes rotations
• sometimes a simple output scrambler such as multiplication or addition

They are popular because they are:

• very fast
• easy to implement
• small enough to study by hand

The core idea

A basic Xorshift generator keeps some internal state x and repeatedly applies a small sequence of XOR-and-shift operations.

For example, a 32-bit Xorshift might look like:

uint32_t xs32(uint32_t x) {
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

The output is often just the updated state itself.

Even though this looks nonlinear at first glance, it is built entirely from operations that are linear over the bits of the state.

The basic variants

Xorshift

This is the simplest form.

The state is updated by a few XOR and shift operations, and the new state is returned as output.

Example:

x ^= x << a
x ^= x >> b
x ^= x << c

This version is extremely instructive because the state transition can often be recovered or inverted directly.

Xorshift*

This variant applies a multiplication after the Xorshift update.

Example:

x = xorshift64(x)
output = x * m mod 2^64

Here m is usually an odd constant.

The multiplication is meant to improve the quality of the output, but it does not make the generator cryptographically secure. In many settings it can be undone or incorporated into an attack.

Xorshift+

This variant usually has a larger state and returns the sum of two state words.

Example idea:

update the internal state
output = s0 + s1 mod 2^64

The + scrambler makes the output less obviously linear, but the generator is still not suitable for cryptographic use.

xoroshiro and xoshiro

These are later descendants of the Xorshift family.

They use:

• XOR
• rotations
• shifts
• small output scramblers such as +, ++, or **

These generators are generally better designed for simulation and general non-cryptographic use, but they are still not cryptographic PRGs.

Why Xorshift is weak against attackers

The key weakness is structure.

For plain Xorshift generators:

• the state transition is linear over GF(2)
• each bit of output is a predictable combination of input bits
• enough output often lets you reconstruct the entire internal state

For scrambled variants like * and +:

• the scrambler may hide the structure a bit
• but the core engine is still highly structured
• if the scrambler is reversible or partially leaked, the state may still be recoverable

Xorshift vs cryptographic PRGs

A cryptographic PRG should make it computationally infeasible to predict future outputs or recover past state from observed output.

Xorshift generators do not provide that guarantee.

They are usually designed for:

• speed
• simplicity
• statistical quality in non-adversarial settings

They are not designed to resist:

• state recovery
• output prediction
• chosen-input or chosen-state attacks
• side-channel style leakage

Why we use them in these challenges

In these challenges, Xorshift generators are not the final goal. They are just the means for learning.

By the end of this module you should come away understanding:

1. How to reason about bitwise state updates.
2. Why XOR-and-shift recurrences can often be inverted.
3. How linear algebra over bits can recover a hidden transition.
4. Why output scrambling does not automatically imply security.
5. Why "fast PRNG" and "secure PRG" are very different goals.

Summary

The Xorshift family is a great introduction to PRG attacks because it exposes the difference between:

• generating numbers that "look random"
• generating numbers that remain secure against an attacker

These generators are fast, elegant, and useful for learning, but they are not safe as cryptographic random number generators.