Pseudorandomness — the series

256 consecutive pairs from xₙ₊₁ = 137xₙ + 187 mod 256. Consecutive outputs of a linear congruential generator plotted as points of a square, falling on a small family of evenly spaced parallel lines.

The planes a recurrence cannot leave

One multiplication and one addition, taken modulo a fixed number, produce a sequence that passes for random one value at a time. Taken two or three at a time it does not, and the reason is a whole-number relation that pins every point onto one of a small family of parallel lines.

part 1 · computation

The same modulus, four multipliers, four qualities. 4 linear generators at modulus 1021, drawn as scatters of consecutive pairs and ranked by the spacing of the lines their points fall on. The spacings differ by more than a factor of two.

The test that ranks the generators

Every linear generator's output lies on a family of parallel planes. Which generator is better is decided by how far apart those planes are, and that distance is the length of the shortest whole-number vector the modulus annihilates — a quantity that can be computed exactly rather than estimated by testing.

part 2 · computation

Four outputs are enough to find the rule. A row of 12 outputs of a linear generator, with the first 4 marked as given and the rest as predicted. The multiplier and increment recovered from the given ones reproduce every later output exactly.

Four numbers and the rule is yours

A linear generator can be solved. Given a few of its outputs, the multiplier and the increment fall out of two congruences, and every future output is then known exactly — which is a failure of a completely different kind from the lattice defect, and is not detected by any test of how evenly the points are spread.

part 3 · computation

Randomness that has to be earned

A generator that resists prediction cannot be built out of a rule anybody can fit. It has to be built out of a computation believed hard to undo, and the belief is the load-bearing part — which makes cryptographic randomness a conditional statement rather than a construction.

part 4 · computation

Every pattern, exactly as often. A table over 4 window lengths of a shift register's output stream: how many bit patterns are possible, how many actually occur, and the difference between the most and least frequent, which is one in every row.

Nineteen thousand bits of state

The generator most simulations actually use is not clever. It is a linear recurrence over the two-element field with an enormous state, and its virtues are a proved period, a proved equidistribution and speed — none of which is unpredictability, which it does not have and does not claim.

part 5 · computation

Fair bits from a biased coin. 44 flips of a coin biased 0.7 towards 1, read in 22 pairs. Mixed pairs are kept and give their first bit; matched pairs are discarded. Over a long run the output is 50.2% ones, at 0.210 output bits per flip.

Fair bits from an unfair coin

Read a biased coin's flips in pairs, keep 01 as 0 and 10 as 1, and throw away the rest: the output is exactly fair, whatever the bias, and nobody needs to know the bias. The trick wastes most of the coin, the waste can be recycled almost up to the ceiling Shannon's entropy sets — and it fails quietly the moment the flips remember each other.

part 6 · computation

How far a filter spreads a generator's output. Bars for bit depths 1 to 8: the ceiling ⌊24/v⌋ outlined, the raw generator's count of evenly spread consecutive outputs (24, 3, 3, 3, 3, 3, 3, 3), and the tempered count (24, 12, 6, 6, 3, 3, 3, 3).

A filter that changes only the spread

The generator most simulations use passes every output through a last scrambling step before anyone sees it. The step is reversible, it changes nothing about the period, and it cannot make the generator any less predictable. What it changes is which patterns of consecutive outputs can occur at all — on a small twisted generator, from half of them to every one.

part 7 · computation

A rectangle of the parity table, nearly balanced. A 32 by 32 grid of +1 and −1 entries — the parity of the inner product of row and column — with a 15 by 14 rectangle of chosen rows and columns highlighted; its entries sum to 8.

Two weak sources make one fair bit

No fixed rule can turn every weakly random source into fair bits: for any rule, some source with almost full unpredictability makes it constant. Two independent sources are different. Multiply their bits in pairs, add, and keep the parity — and if the two together carry more unpredictability than the length of one, the result is nearly fair, whatever else the sources do. The reason is that the table of those parities is balanced on every large rectangle.

part 8 · computation

The low bits of a congruential generator, and the bits a permutation shows. First 128 steps of a 16-bit congruential generator: low state bits with periods 2, 4, 8, 16, 32, 64, 128, 256; permuted output bits all with period 65536.

A rotation that hides the lattice

A congruential generator modulo a power of two has a lowest bit that alternates and pairs of outputs that lie on a few lines. Keep the generator exactly as it is, and show only eight bits of each state, rotated by an amount the state's own top bits choose: every output bit now runs the full cycle, the pairs fill the square as a random sequence would, and triples pass a test the state's own bits fail by a factor of six. Nothing about the state has changed, and four outputs still give it away.

part 9 · computation

Four seeds of the middle-square method, each until it repeats. Values against step for the four-digit seeds 6239, 1234, 5735, 4100 under the middle-square rule, each ending where a value repeats: after 111, 57, 31, 4 steps.

Square it and keep the middle

John von Neumann's first generator of random numbers squared a number and kept its middle digits. Followed from every four-digit seed, it never lasts more than 111 steps before a value repeats — a third of what the birthday problem allows a truly random rule — and one seed in five ends at zero for ever. A counter added before each squaring cures the collapse.

part 10 · computation

Two grids of random-looking bits, one of rank thirty-two. 48 by 48 bit matrices: xorshift32 low bits, rank 32; xorshift32 multiplied, rank 47.

A grid of bits whose rank stops at the state

Fill a square grid with a generator's output bits and compute its rank over the field of two elements. Random bits give full rank or one short, in fixed proportions. A generator built from shifts and exclusive-ors gives full rank up to its number of state bits and then never one more — 32 for a 32-bit xorshift, 128 for the lowest bit of xorshift128+ — however large the grid. The test that catches it is decided by a line of linear algebra.

part 11 · computation