1
Collisions are guaranteed
More keys than slots means some slot is shared — the pigeonhole principle. The design question is how collisions are handled, not whether they occur.
Lesson · Number Theory and Cryptography · Applications
Hashing and Pseudorandom Numbers
Hash functions map keys to a small range with mod, and linear congruential generators produce pseudorandom sequences the same way. Both work because of number theory, and both fail in ways number theory predicts.
h(k) = k mod m a hash function
collisions are unavoidable (pigeonhole)
xₙ₊₁ = (a·xₙ + c) mod m linear congruential generator
full period ⟺ Hull–Dobell conditions on a, c, m
Modular arithmetic, applied
Core ideas
What this lesson establishes
Two applications where the choice of modulus decides whether the method works or fails badly.
2
A prime modulus spreads better
k mod 2^r uses only the low bits of the key, so structured keys collide heavily. A prime modulus uses all of them.
3
Pseudorandom is not random
An LCG is completely determined by its seed. It looks random by some statistical measures and is entirely predictable, which matters for security.
The material
Hashing and pseudorandomness
Both constructions, the number theory behind them, and their failure modes.
Hash functions
Definition · Hash function
A function h mapping a large key space into {0, 1, …, m−1}. The simplest is h(k) = k mod m.
Since the key space is larger than the range, collisions are unavoidable: by the pigeonhole principle of “The Pigeonhole Principle” in Sets, Relations, and Functions, some slot receives more than one key. A hash table is therefore designed around collisions — by chaining, or by probing for another slot.
Theorem · Why the modulus should be prime
If m = 2^r, then k mod m depends only on the low r bits of k. Keys sharing those bits — addresses aligned to a boundary, identifiers with a common suffix — all collide. A prime modulus has no such structure to exploit.
Example · A bad choice
Hashing memory addresses with m = 16 when every address is a multiple of 16 sends every key to slot 0. With m = 17 the same keys spread across all seventeen slots.
The birthday problem of “Computing Probabilities” in Discrete Probability gives the collision rate: with m slots and n keys, collisions become likely once n is around √m. A table of a million slots sees its first collision after about a thousand insertions, which is why load factors are managed rather than collisions avoided.
Linear congruential generators
Definition · LCG
x_{n+1} = (a·x_n + c) mod m, from a seed x₀. The parameters a (multiplier), c (increment) and m (modulus) determine the whole sequence.
The sequence must eventually repeat, since there are only m possible values — pigeonhole again. The period is how long it takes, and it is at most m.
Theorem · Hull-Dobell theorem
An LCG has full period m for every seed if and only if: gcd(c, m) = 1; a − 1 is divisible by every prime dividing m; and a − 1 is divisible by 4 if m is.
Example · A bad generator
a = 5, c = 3, m = 8, seed 0: 0, 3, 2, 5, 4, 7, 6, 1, 0, … — full period 8, and the conditions hold. Change a to 4 and the sequence is 0, 3, 7, 7, 7, …: it collapses almost immediately, because a − 1 = 3 is not divisible by 2.
Even a full-period LCG is not statistically good. Consecutive values fall on a small number of hyperplanes in higher dimensions — the Marsaglia effect — and the low bits of a power-of-two-modulus LCG have very short periods. RANDU, an LCG shipped by IBM in the 1960s, was so bad in three dimensions that results computed with it were later retracted.
Cryptographic requirements are different
An LCG is trivially predictable: observing a few outputs determines the parameters and hence every future value. That is fine for a simulation and fatal for a key or a session token. Cryptographic generators are built so that predicting the next output is as hard as a problem believed intractable — and "looks random" is not the same requirement as "cannot be predicted".
Interactive
Number theory workbench
Algorithms with their traces
Method
Choosing parameters
The modulus decides the behaviour.
1
For a hash table, prefer a prime modulus
It uses all the bits of the key. A power of two uses only the low ones, which is where structured keys collide.
2
Expect collisions and plan for them
Chaining or open addressing. By the birthday argument they begin around √m insertions.
3
For an LCG, check the Hull-Dobell conditions
They guarantee full period. Failing them can collapse the sequence to a handful of values.
4
Never use an LCG where prediction matters
Session tokens, keys and nonces need a cryptographic generator. The distinction is about predictability, not about statistics.
Hashing and randomness
Score 0 / 0Choose the answer you can justify.
Two generators, same modulus
m = 16, seed 1, comparing a good and a bad multiplier.
a = 5, c = 3 Hull–Dobell: gcd(3,16)=1 ✓ 2 | (a−1)=4 ✓ 4 | 4 ✓
1, 8, 11, 10, 5, 12, 15, 14, 9, 0, 3, 2, 13, 4, 7, 6, 1, …
period 16 — every value once ✓
a = 6, c = 3 gcd(3,16)=1 ✓ but 2 ∤ (a−1)=5 ✗
1, 9, 9, 9, …
period 1 after the first step — the generator is dead
One parameter changed by 1, and the sequence went from
every value to a constant.
This is why the theorem is worth having. The failure is not a degradation — it is total, and it would be easy to ship without noticing if the seed happened to look fine. The conditions are three divisibility checks.
Common mistakes
1
Using a power of two as a hash modulus with structured keysOnly the low bits matter, so aligned or suffixed keys cluster. A prime modulus removes the structure.
2
Assuming a full-period LCG is statistically goodFull period is necessary and far from sufficient. Consecutive tuples fall on hyperplanes, which broke real scientific results.
3
Using a general-purpose generator for security"Looks random" and "cannot be predicted" are different properties, and only the second matters for keys.
Check your understanding
✓
Finish when you can check the Hull-Dobell conditions.
For m = 100, find a multiplier and increment giving full period, and one that fails. The three conditions are quick to verify and the failure is dramatic.
Note: Cryptographic hash functions — SHA-256 and the like — are a different object from the hash functions here: they must also be collision-resistant against an adversary who is trying, which is a requirement k mod m does not begin to meet.