Day 79 — RNG, LCG, randomness literacy

Updated

July 30, 2026

Day 79 — Random number generators, LCGs, and randomness literacy

Stage VII · concept day
Goal: Define LCG \(x_{n+1}=(ax_n+c)\bmod m\); state Hull–Dobell full-period criterion; separate entropy vs PRNG; discuss seeds; cryptographic vs statistical randomness ideas; von Neumann caution.

Why this matters

“Random” in programs usually means pseudorandom: deterministic sequences that pass statistical tests. Modular arithmetic is the engine of classical linear congruential generators. Confusing PRNG streams with cryptographic keys is a perennial systems failure mode. Today is mathematical + conceptual literacy — still no labs.

Note

No labs / no implementing generators for production. Hand-trace tiny LCGs; write conceptual comparisons. Do not treat this as a CSPRNG design course.

Theory

True randomness vs pseudorandomness

True / physical randomness (idea): outcomes modeled as unpredictable even given all prior observations (radioactive decay, thermal noise) — idealized. Entropy (Shannon literacy): a measure of uncertainty; a fair bit has \(1\) bit of entropy. Collecting entropy is an engineering problem (OS entropy pools) — awareness only.

PRNG (pseudorandom number generator): a deterministic algorithm that expands a short seed into a long sequence that appears random for statistical purposes. Same seed ⇒ same sequence (reproducibility — good for simulations; bad if seed is secret-critical and leaked).

CSPRNG (cryptographically secure PRNG): a PRNG that is unpredictable to an adversary (next-bit unpredictability) under computational assumptions. Statistical goodness is necessary but not sufficient for crypto.

Linear congruential generator (LCG)

Definition. An LCG is defined by modulus \(m>0\), multiplier \(a\), increment \(c\), and seed \(x_0\): \[ x_{n+1} = (a x_n + c)\bmod m. \] The output is often \(x_n\), or \(x_n/m\) as a faux-uniform in \([0,1)\).

Parameters: integers, typically \(0\le a,c,x_0<m\).

Period. The sequence is eventually periodic because there are only \(m\) states. The period is the smallest \(T>0\) such that the sequence of states repeats with period \(T\) (for a full cycle from the start, we care about the period of the orbit of \(x_0\)).

Maximum period. At most \(m\) distinct states, so period \(\le m\). Full period means period \(m\) (visits every residue before repeating) — only possible if the map is a single \(m\)-cycle on \(\mathbb{Z}/m\mathbb{Z}\).

Hull–Dobell theorem (statement)

Theorem (Hull–Dobell). The LCG \(x\mapsto (ax+c)\bmod m\) has full period \(m\) for all seeds iff:

  1. \(\gcd(c,m)=1\) (increment coprime to modulus);
  2. \(a\equiv 1\pmod p\) for every prime \(p\) dividing \(m\);
  3. \(a\equiv 1\pmod 4\) if \(4\mid m\).

Use. A criterion to check, not something we prove fully in this volume. Special case \(c=0\) (multiplicative congruential): full period \(m\) is impossible for all seeds; periods divide \(\lambda(m)\) structure — different theory (max period \(m-1\) when \(m\) prime and \(a\) primitive root, etc.).

Examples of structure

  • \(m=2^{32}\) historically common for machine words — low bits of LCG output can be highly regular.
  • RANDU (infamous): \(a=65539\), \(c=0\), \(m=2^{31}\) — strong lattice correlations (awareness).
  • Tiny full-period example: \(m=8\), \(a=5\), \(c=3\): check Hull–Dobell: \(\gcd(3,8)=1\); primes dividing \(8\) only \(2\), \(a=5\equiv 1\pmod 2\); \(4\mid 8\) and \(5\equiv 1\pmod 4\). Full period expected.

Seed

Definition. The seed is the initial state \(x_0\) (sometimes a vector of states for more complex PRNGs).

Requirements by use case:

Use Seed needs
Monte Carlo debug Fixed seed for reproducibility
Simulation variety Different seeds; statistical quality
Cryptographic keys / nonces High-entropy secret seed; CSPRNG

Never seed a security-critical generator with time() alone if an adversary can guess the second.

Statistical vs cryptographic randomness

Statistical tests (idea): look at frequency of bits, runs, poker tests, spectral tests for LCGs — detect obvious bias. Passing tests ≠ secure.

Cryptographic requirements (ideas):
- Next-bit unpredictability: given previous outputs, next bit should not be predictable with probability much better than \(1/2\).
- State compromise resilience (stronger designs): past/future outputs hard given state leak at a time (design-dependent).
- LCGs are not CSPRNGs: state is small; outputs leak linear structure; can often reconstruct state from few outputs.

von Neumann caution

von Neumann (paraphrase): “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”

Reading for this course: Pseudorandom arithmetic is powerful and legitimate for simulation when understood; it is not “true randomness,” and using weak PRNGs for crypto is the sin that matters practically. Deterministic generators cannot create entropy — they only stretch seed entropy.

Sampling bias via modular reduction

Pitfall. If you need a uniform number in \(\{0,\ldots,k-1\}\) and take \(x\bmod k\) where \(x\) is uniform in \(\{0,\ldots,m-1\}\) and \(m\not\equiv 0\pmod k\), the distribution is slightly biased toward smaller residues.

Exact: residues \(r\) with \(r<m\bmod k\) appear \(\lfloor m/k\rfloor+1\) times; others \(\lfloor m/k\rfloor\) times.

Literacy fix: rejection sampling (discard draws in the incomplete last block) — idea only.

Other generators (awareness names)

LFSR / Mersenne Twister (excellent statistical properties for sim; not crypto), PCG, xorshift, OS CSPRNG (getrandom, /dev/urandom models). Know names; no deep dive.

Worked examples

Example 1 — Hand LCG.
\(m=10\), \(a=3\), \(c=1\), \(x_0=0\):
\(0,1,4,3,0,1,\ldots\) period \(4\) (not full). Hull–Dobell fails: \(a=3\not\equiv 1\pmod 2\).

Example 2 — Full period candidate.
\(m=8\), \(a=5\), \(c=3\), \(x_0=0\):
\(x_1=(0+3)=3\), \(x_2=5\cdot 3+3=18\equiv 2\), \(x_3=5\cdot 2+3=13\equiv 5\), \(x_4=5\cdot 5+3=28\equiv 4\), \(x_5=5\cdot 4+3=23\equiv 7\), \(x_6=5\cdot 7+3=38\equiv 6\), \(x_7=5\cdot 6+3=33\equiv 1\), \(x_8=5\cdot 1+3=8\equiv 0\). Period \(8\). ✓

Example 3 — Multiplicative.
\(m=7\), \(a=3\), \(c=0\), \(x_0=1\): \(1,3,2,6,4,5,1,\ldots\) period \(6=m-1\). Visits all nonzero residues.

Example 4 — Seed reproducibility.
Same \((m,a,c,x_0)\) ⇒ identical stream. “Random” UI that always reseeds with \(1\) is not random across runs.

Example 5 — Modular bias.
\(m=10\), want uniform in \(\{0,1,2\}\): values \(0..9\) mod \(3\) give residues \(0,1,2,0,1,2,0,1,2,0\) — counts \(4,3,3\). Slight excess of \(0\).

Example 6 — Hull–Dobell fail.
\(m=12\), \(a=5\), \(c=1\): \(\gcd(1,12)=1\); prime \(2\mid 12\), \(5\equiv 1\pmod 2\) OK; prime \(3\mid 12\), \(5\equiv 2\not\equiv 1\pmod 3\). Fail. Period will be \(<12\).

Example 7 — Crypto misuse.
Using LCG output as AES key material: adversary who sees outputs can often recover state and predict future keys. Statistical “looks random” is irrelevant.

Example 8 — Entropy stretch.
\(128\) bits of seed entropy into a CSPRNG can produce gigabytes of output that remains unpredictable if the CSPRNG is secure and seed is secret — but information-theoretically the entire stream has only \(128\) bits of entropy; computational hardness is the point.

Exercises

A. LCG traces

  1. Trace LCG \(m=16\), \(a=5\), \(c=1\), \(x_0=0\) for \(20\) steps; find the period from \(x_0\).
  2. Trace \(m=16\), \(a=5\), \(c=3\), \(x_0=0\); check Hull–Dobell conditions.
  3. For \(m=9\), \(a=4\), \(c=2\), \(x_0=1\), list the orbit until repeat.
  4. Multiplicative: \(m=11\), \(a=2\), \(c=0\), \(x_0=1\) — period?
  5. Show that if \(c=0\) and \(\gcd(x_0,m)>1\), the sequence never hits \(1\).

B. Hull–Dobell

  1. State Hull–Dobell fully from memory.
  2. Which of \((m,a,c)=(10,3,1)\), \((8,5,3)\), \((9,4,1)\), \((15,4,2)\) can have full period?
  3. Design a full-period LCG with \(m=20\) (find \(a,c\) satisfying the theorem).
  4. Why does condition (1) \(\gcd(c,m)=1\) make sense if you think about gcd of successive differences?
  5. Prove period divides… (stretch): for pure multiplicative LCG mod prime, period divides \(p-1\).

C. Bias and sampling

  1. \(x\) uniform in \(\{0,\ldots,15\}\), output \(x\bmod 6\). Count multiplicity of each residue \(0..5\).
  2. Describe rejection sampling to get uniform \(\{0,1,2\}\) from uniform \(\{0..15\}\).
  3. If \(m\) is divisible by \(k\), show \(x\bmod k\) is uniform when \(x\) is uniform mod \(m\).

D. Conceptual literacy

  1. Contrast PRNG vs CSPRNG in a table of 4 rows (reproducibility, entropy source, adversary model, typical use).
  2. Why is “pass Diehard tests” not a crypto certificate?
  3. Explain von Neumann’s caution in your own words (4–6 sentences) without dismissing simulation.
  4. Seed hygiene: list three bad seeds for security contexts.
  5. Why might low bits of an LCG with power-of-two modulus be nonrandom?

E. Stretch

  1. Show the LCG map \(f(x)=ax+c\) on \(\mathbb{Z}/m\mathbb{Z}\) is bijective iff \(\gcd(a,m)=1\) (for the \(c=0\) case clarity) — actually for affine \(f\), bijective iff \(\gcd(a,m)=1\).
  2. Prove: if \(f\) is bijective then every orbit structure is a permutation consisting of cycles; full period means one single cycle of length \(m\).
  3. Historical literacy: one paragraph on why Mersenne Twister became popular for simulations and why it is still wrong for keys.
  4. Connect Day 76: using PRNG to pick hash functions from a universal family — what must be true of the PRNG for the analysis to be honest?

Deep dive — Hull–Dobell checklist worked

For candidate \((m,a,c)\):

  1. Compute \(\gcd(c,m)\) — must be \(1\).
  2. Factor \(m\); for each prime \(p\mid m\), check \(a\equiv 1\pmod p\).
  3. If \(4\mid m\), check \(a\equiv 1\pmod 4\).

Example. \(m=2^4=16\), \(a=5\), \(c=1\): (1) \(\gcd(1,16)=1\); (2) only prime \(2\), \(5\equiv 1\pmod 2\); (3) \(5\equiv 1\pmod 4\). Full period possible. Trace a seed to confirm length \(16\).

Counterexample. \(m=15=3\cdot 5\), \(a=4\), \(c=1\): \(\gcd(1,15)=1\); \(4\not\equiv 1\pmod 3\). Fail.

Deep dive — entropy accounting (ideas)

  • A fair coin flip: \(1\) bit of entropy.
  • A password from a space of size \(N\) under uniform: \(\log_2 N\) bits if uniform and secret.
  • A PRNG with \(128\)-bit seed: at most \(128\) bits of entropy in the entire infinite output stream (information-theoretically). Computational security claims the outputs still look random to efficient adversaries.
  • Reusing a seed across security contexts collapses independence assumptions.

Additional worked examples

Example 9 — Period of multiplicative LCG.
\(m=13\) prime, \(a=2\), \(c=0\), \(x_0=1\): powers of \(2\) mod \(13\): \(2,4,8,3,6,12,11,9,5,10,7,1\) — period \(12=m-1\).

Example 10 — Bad power-of-two low bits.
\(m=16\), \(a=5\), \(c=1\): sequence parity of \(x_n\) often highly patterned; examining \(x_n\bmod 4\) can look nonrandom even when full period holds.

Example 11 — Rejection sampling.
Want uniform \(\{0,1,2\}\) from uniform \(\{0,\ldots,15\}\). Accept \(0..14\) mapped as \(r\bmod 3\)? Better: accept only \(0..14\) if using blocks of \(3\), or accept \(x\) if \(x<15\), output \(x\bmod 3\) with equal counts \(5\) each — wait \(15\) values → \(5\) each for residues mod \(3\). Discard \(15\).

Example 12 — Seed collision.
Two users seed with timestamp at same second → identical “random” UUIDs — classic outage story (literacy).

Example 13 — Statistical vs crypto table.

Test PRNG for sim CSPRNG
Reproducible stream Desired Seed secret; still deterministic
Diehard/NIST pass Goal Necessary not sufficient
State recover from output Often easy (LCG) Should be hard
Use for keys Never Yes (if API correct)

More exercises

  1. Trace full period LCG \(m=9,a=4,c=1\) or show Hull–Dobell fails.
  2. Prove affine map \(x\mapsto ax+c\) on \(\mathbb{Z}/m\mathbb{Z}\) bijective iff \(\gcd(a,m)=1\).
  3. For \(m=100\), can \(c=0\) give full period \(100\)? Why/why not?
  4. Compute bias: uniform \(0..255\) mod \(10\) — counts per digit.
  5. Write 6–8 sentences: when is a fixed seed a feature?
  6. Name three CSPRNG/OS interfaces (culture) and one misuse.
  7. LCG \(m=7,a=3,c=0\): list all orbits by seed.
  8. Connect to Day 76: sampling a universal hash key with weak RNG fails the model.

Selected mini-solutions

  1. Hull–Dobell for \((16,5,3)\): \(\gcd(3,16)=1\); \(5\equiv 1\pmod 2\); \(5\equiv 1\pmod 4\) — OK.
  2. Full period candidates must pass all three conditions — check each tuple.
  3. Residues \(0..15\bmod 6\): counts \(3,3,3,3,2,2\) for \(0..5\).
  4. Bijective iff \(\gcd(a,m)=1\) for \(f(x)=ax+c\).

Common pitfalls

Pitfall Fix
Equating “random-looking” with secure Crypto needs unpredictability
Assuming all LCGs have period \(m\) Hull–Dobell required
Seeding with predictable time Guessable seed ⇒ guessable stream
Ignoring modular sampling bias Rejection or careful ranges
Implementing crypto PRNG from LCG Never
Thinking PRNG creates entropy Only stretches seed entropy

Study notes — randomness vocabulary

Term One-line
Entropy Uncertainty measure; fair bit = 1 bit
Seed Initial PRNG state
LCG \(x\leftarrow(ax+c)\bmod m\)
Full period Visits all \(m\) states (Hull–Dobell)
PRNG Deterministic stretch of seed
CSPRNG Unpredictable under compute bounds
Sampling bias \(x\bmod k\) when \(m\nmid k\) uneven

von Neumann: arithmetic methods stretch, they do not create, true randomness.

Synthesis — RNG literacy workout

S1. State Hull–Dobell; test \((m,a,c)=(20,11,1)\).

S2. Trace LCG \(m=11,a=3,c=0,x_0=1\) until period found.

S3. Prove \(x\mapsto ax+c\) bijective on \(\mathbb{Z}/m\mathbb{Z}\) iff \(\gcd(a,m)=1\).

S4. Counts: uniform \(\{0,\ldots,20\}\) reduced mod \(6\) — multiplicity of each residue.

S5. Table: PRNG vs CSPRNG vs physical entropy — 4 contrast rows.

S6. von Neumann caution: rewrite in your words with a modern example (LCG keys).

S7. Why power-of-two moduli make low bits weak for some LCGs.

S8. Seed hygiene checklist (5 bullets) for non-crypto sim vs crypto keys.

Checkpoint

  • Can define LCG and hand-trace periods
  • Can state Hull–Dobell full-period criterion
  • Can explain entropy vs PRNG stretch
  • Can separate statistical vs cryptographic randomness
  • Can explain modular sampling bias
  • Exercises A–D done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — when is the LCG map a single \(m\)-cycle?

Bijectivity first. \(f(x)=ax+c\bmod m\) is bijective iff \(\gcd(a,m)=1\). Proof: if \(\gcd(a,m)=1\), inverse map \(x\mapsto a^{-1}(x-c)\); if \(\gcd(a,m)=d>1\), then \(f(0)=c\) and \(f(m/d)=a(m/d)+c\equiv c\pmod m\) when \(d\mid a\) carefully — more simply \(f(x)=f(y)\) iff \(a(x-y)\equiv 0\pmod m\), nontrivial kernel if \(\gcd(a,m)>1\).

Full period is stronger than bijective. A bijection on a finite set is a permutation and decomposes into cycles. Full period for all seeds means the permutation is a single \(m\)-cycle. Hull–Dobell gives exactly the arithmetic conditions for that.

Multiplicative case \(c=0\). \(f(x)=ax\bmod m\) always fixes \(0\). Cannot be a single \(m\)-cycle. Maximal period on \(\{1,\ldots,m-1\}\) when \(m\) prime and \(a\) primitive root is \(m-1\).

Deeper theory — modular reduction bias formula

If \(X\) is uniform on \(\{0,1,\ldots,m-1\}\) and \(R=X\bmod k\), then for \(r\in\{0,\ldots,k-1\}\), \[ P(R=r)=\frac{\lfloor m/k\rfloor}{m}\quad\text{or}\quad\frac{\lfloor m/k\rfloor+1}{m}, \] with the larger probability on \(r<m\bmod k\). Bias vanishes iff \(k\mid m\).

Rejection sampling (idea). Draw \(X\); if \(X\ge k\lfloor m/k\rfloor\), reject and redraw; else output \(X\bmod k\). Uniform on \(\{0,\ldots,k-1\}\).

Worked examples — more LCG traces

Example 14 — Full period \(m=16\), \(a=5\), \(c=1\), \(x_0=0\).
Hull–Dobell OK (earlier). Trace: \(0,1,6,15,12,13,2,11,8,9,14,7,4,5,10,3,0\) — sixteen distinct values. ✓

Example 15 — Fail period \(m=15\), \(a=4\), \(c=1\).
\(4\not\equiv 1\pmod 3\). Orbit from \(0\): \(0,1,5,6,10,11,0\) — period \(6<15\).

Example 16 — Bias counts \(m=256\), \(k=10\).
\(\lfloor 256/10\rfloor=25\), remainder \(6\), so residues \(0..5\) appear \(26\) times, \(6..9\) appear \(25\) times. Slight excess of low digits.

Example 17 — Entropy stretch numerical.
\(64\)-bit seed CSPRNG: at most \(2^{64}\) possible streams. After \(2^{40}\) outputs, birthday collisions among seeds become a threat if seeds were low-entropy — seed quality dominates.

Extra exercises — RNG literacy

  1. Trace \(m=12\), \(a=7\), \(c=1\), \(x_0=0\) for \(15\) steps; report period.
  2. Check Hull–Dobell for \((m,a,c)=(24,13,5)\).
  3. Prove bijectivity criterion for \(x\mapsto ax+c\bmod m\).
  4. Counts for uniform \(\{0..99\}\) mod \(7\).
  5. Why is \(c=0\), \(m=2^{31}\), \(a=65539\) (RANDU) historically notorious? (One paragraph: lattice structure awareness.)
  6. Design full-period LCG with \(m=10\) if possible; if not, explain which condition fails for candidates.
  7. Seed hygiene: rank time(), /dev/urandom, constant 1, user password entropy — for crypto keys.
  8. Connect: sampling universal hash family with LCG seed of \(16\) bits — attack surface in one paragraph.

Mini-solutions (selected)

  1. \(\gcd(5,24)=1\); primes \(2,3\mid 24\): \(13\equiv 1\pmod 2\) OK, \(13\equiv 1\pmod 3\) OK; \(4\mid 24\), \(13\equiv 1\pmod 4\) OK — full period candidate.
  2. \(ax+c\equiv ay+c\Rightarrow a(x-y)\equiv 0\pmod m\); solvable uniquely for \(x\) given \(y\) iff \(\gcd(a,m)=1\).
  3. \(m=10=2\cdot 5\): need \(a\equiv 1\pmod 2\) and \(a\equiv 1\pmod 5\), so \(a\equiv 1\pmod{10}\), \(a=1\); \(\gcd(c,10)=1\). E.g. \((10,1,1)\) works but multiplier \(1\) is degenerate-looking (still full period theoretically).

Closing synthesis card

Concept Own it?
LCG definition □
Hull–Dobell three conditions □
PRNG ≠ CSPRNG □
Seed entropy □
\(x\bmod k\) bias □
von Neumann caution □

Tomorrow

Day 80 — Gate VII (number theory for CS mixed dossier).