Day 27 — Crypto Math, CRT, PRNGs & Gate VII

Updated

July 30, 2025

Day 27 — Crypto Math, CRT, PRNGs & Gate VII

Day 77 — Diffie–Hellman and RSA as mathematical stories

Stage VII · concept day
Goal: Follow the algebra of Diffie–Hellman key agreement and RSA encrypt/decrypt with toy parameters; state discrete log and factoring hardness as assumptions; practice parameter literacy; no production implementation.

Why this matters

Public-key ideas are applications of modular exponentiation, inverses, and Euler’s theorem. Understanding the story demystifies protocol diagrams. Misunderstanding leads to cargo-cult crypto. This day is mathematical literacy with toy numbers.

Important

Not production crypto. No implement-RSA lab, no “roll your own” protocol. Toy moduli only. Real systems use vetted libraries, padding schemes, modern curves/parameters, and constant-time engineering far beyond this course. Attack names appear as awareness only.

Theory

One-way intuition

A function \(f\) is easy to compute but hard to invert (informally) if \(y=f(x)\) is cheap given \(x\), yet recovering \(x\) from \(y\) is infeasible at scale.

Direction DH world RSA world
Easy \(g^a\bmod p\) given \(g,a,p\) \(m^e\bmod n\) given \(m,e,n\)
Believed hard (generic) Discrete log: given \(g,p,g^a\bmod p\), find \(a\) Factor \(n=pq\); or extract \(e\)-th roots without trapdoor

These are assumptions, not theorems you prove today.

Discrete logarithm problem (statement)

Definition (DLP). Given prime \(p\), generator (or base) \(g\), and \(h\equiv g^x\bmod p\), recover the secret exponent \(x\) (often in \(\{0,\ldots,p-2\}\)).

Hardness (literacy). For carefully chosen large \(p\) and \(g\), no efficient classical algorithm is known for general DLP; hardness is an assumption underlying DH and many classical public-key systems. (Quantum algorithms change the story — awareness only: Shor.)

Diffie–Hellman key exchange (math)

Public parameters: large prime \(p\) and base \(g\) (often a generator mod \(p\), or element of large order).

Protocol algebra:

  1. Alice picks secret \(a\), sends \(A\equiv g^a\bmod p\).
  2. Bob picks secret \(b\), sends \(B\equiv g^b\bmod p\).
  3. Alice computes \(K\equiv B^a=(g^b)^a=g^{ab}\bmod p\).
  4. Bob computes \(K\equiv A^b=(g^a)^b=g^{ab}\bmod p\).

Shared secret: \(K=g^{ab}\bmod p\).

Eavesdropper sees: \(p,g,A,B\). Computing \(K\) from these is the Computational Diffie–Hellman (CDH) problem; extracting \(a\) from \(A\) is DLP. CDH is not known to be equivalent to DLP in all groups, but both are believed hard in standard groups.

What DH does not provide alone: authentication (man-in-the-middle is a protocol issue). Literacy: math equality of keys ≠ full secure channel.

RSA key generation (math)

  1. Choose distinct large primes \(p,q\).
  2. Compute modulus \(n=pq\) and \(\varphi(n)=(p-1)(q-1)\) (or \(\lambda(n)=\mathrm{lcm}(p-1,q-1)\) in modern variants — awareness).
  3. Choose encryption exponent \(e\) with \(\gcd(e,\varphi(n))=1\) (common toy/historic \(e=3\) or \(65537\) in practice).
  4. Compute \(d\) with \(ed\equiv 1\pmod{\varphi(n)}\) (modular inverse via extended Euclid).
  5. Public key: \((n,e)\). Private key: \(d\) (and usually \(p,q\) retained for speed/CRT).

RSA encrypt / decrypt theorem

Message \(m\) with \(0\le m<n\) and typically \(\gcd(m,n)=1\) for the clean Euler argument (real systems use padding so \(m\) is structured).

  • Encrypt: \(c\equiv m^e\bmod n\).
  • Decrypt: \(m'\equiv c^d\bmod n\).

Theorem (RSA correctness, Euler form). If \(\gcd(m,n)=1\) and \(ed\equiv 1\pmod{\varphi(n)}\), then \[ m^{ed}\equiv m\pmod n. \] Proof sketch. \(ed=1+t\varphi(n)\), so \[ m^{ed}=m\cdot (m^{\varphi(n)})^t\equiv m\cdot 1^t\equiv m\pmod n \] by Euler’s theorem. (When \(\gcd(m,n)\neq 1\), correctness still holds for \(n=pq\) by CRT + Fermat on each prime factor — sketch: prove \(m^{ed}\equiv m\pmod p\) and mod \(q\).)

Parameter size literacy (order of magnitude)

Era / culture RSA modulus \(n\) Notes
Toy classroom \(10^2\)–\(10^4\) For hand arithmetic only
Historical 512-bit broken Do not use
Modern ballpark 2048-bit+ RSA common; 3072+ for long term Follow current standards, not this book
DH primes / groups Large safe primes or standard named groups Use standards

Moral: classroom \(n=55\) explains algebra; it provides zero security.

Attacks awareness (names only)

Know the names and one-line idea; do not implement:

Name One-line idea
Trial division / Fermat factoring Factor small or close \(p,q\)
Pollard’s rho / NFS Subexponential factoring families
Wiener’s attack Small private \(d\) vulnerable
Hastad broadcast Same \(m\), small \(e\), many moduli
Plain RSA without padding Multiplicative malleability; dictionary attacks on small \(m\)
Man-in-the-middle on raw DH No authentication of \(A,B\)
Timing / side channels Engineering leak of \(d\) or bits (not number theory alone)

What this day is not

  • Not a substitute for a cryptography engineering course.
  • Not a license to use raw RSA or textbook DH in software.
  • Not covering elliptic curves, AEAD, signatures, TLS handshake details.

Worked examples

Example 1 — Tiny DH.
\(p=23\), \(g=5\). Alice \(a=6\): \(A=5^6\bmod 23\). \(5^2=25\equiv 2\), \(5^4\equiv 4\), \(5^6=5^4\cdot 5^2\equiv 4\cdot 2=8\bmod 23\).
Bob \(b=15\): \(B=5^{15}\bmod 23\). (Compute stepwise: \(5^1=5\), \(5^2=2\), \(5^3=10\), \(5^4=4\), \(5^5=20\), … or binary.)
Shared: \(K=B^6\bmod 23=A^{15}\bmod 23\). Verify both paths with careful powering — the equality is the lesson.

Example 2 — Tiny RSA keygen.
\(p=5\), \(q=11\), \(n=55\), \(\varphi=4\cdot 10=40\). Choose \(e=3\) (\(\gcd(3,40)=1\)). Inverse: \(3d\equiv 1\pmod{40}\) ⇒ \(d=27\) because \(81\equiv 1\pmod{40}\).

Example 3 — RSA encrypt/decrypt.
\(m=7\), \(c=7^3=343\bmod 55\). \(343=6\cdot 55+13\) ⇒ \(c=13\). Decrypt: \(13^{27}\bmod 55\). Use successive squaring or Euler: since \(\gcd(13,55)=1\), \(13^{40}\equiv 1\), and \(27\) is smaller — compute carefully by hand or stepwise: \(13^2=169\equiv 4\pmod{55}\), \(13^4\equiv 16\), \(13^8\equiv 36\), etc. Final should return \(7\). (Do the full ladder in exercises.)

Example 4 — Why \(ed\equiv 1\pmod{\varphi(n)}\).
\(ed=1+t\varphi(n)\) feeds Euler directly. If you only had \(ed\equiv 1\pmod n\), that would be wrong modulus for exponents.

Example 5 — Failed \(e\).
\(n=55\), \(\varphi=40\), \(e=5\): \(\gcd(5,40)=5\neq 1\), no inverse \(d\).

Example 6 — DLP toy.
\(p=23\), \(g=5\), \(h=8\). Find \(x\) with \(5^x\equiv 8\pmod{23}\). From Example 1, \(x=6\) works. Brute force is fine for \(p=23\); impossible by hand for \(300\)-digit \(p\).

Example 7 — Correctness when \(\gcd(m,n)\neq 1\).
\(m=5\), \(n=55\), \(e=3\), \(d=27\). Then \(m\) shares factor with \(n\). Still \(m^{ed}\equiv m\pmod{55}\) holds by CRT argument — check numerically small powers if desired.

Example 8 — Parameter literacy.
A \(10\)-bit prime is \(\sim 3\) digits; a \(1024\)-bit modulus is \(\sim 308\) decimal digits. Classroom RSA is not “almost real.”

Exercises

A. Discrete log and DH

  1. State the discrete log problem carefully with all inputs/outputs.
  2. With \(p=11\), \(g=2\), compute \(2^a\bmod 11\) for \(a=1,\ldots,10\). Is \(g\) a generator?
  3. DH toy: \(p=11\), \(g=2\), \(a=4\), \(b=3\). Compute \(A\), \(B\), and shared \(K\) both ways.
  4. Why does an eavesdropper who can solve DLP break this DH instance?
  5. Explain MITM on DH in one paragraph (protocol, not algebra failure).

B. RSA keygen

  1. For \(p=7\), \(q=13\), compute \(n\), \(\varphi(n)\). Find an \(e\) with \(1<e<\varphi(n)\) and \(\gcd(e,\varphi)=1\). Compute \(d\).
  2. Same for \(p=11\), \(q=17\), \(e=7\).
  3. Show that \(e=21\) fails for \(n=55\) (\(\varphi=40\)).
  4. Prove: if \(ed\equiv 1\pmod{\varphi(n)}\) and \(\gcd(m,n)=1\) then \(m^{ed}\equiv m\pmod n\).
  5. Why is the private key \(d\) not simply \(1/e\) in rationals?

C. Encrypt/decrypt (toy)

  1. Using \(n=55\), \(e=3\), \(d=27\), encrypt \(m=8\) and decrypt the ciphertext (hand modular powering).
  2. Encrypt \(m=9\) with the same key; decrypt.
  3. Verify \(ed=81=2\cdot 40+1\).
  4. If someone publishes \(p\) and \(q\) by mistake, show how to compute \(d\) from \(e\).
  5. Explain why encrypting \(m=0\) or \(m=1\) is a terrible idea in textbook RSA (no padding).

D. Literacy and attacks (names)

  1. Match attack name to description: Wiener / Hastad / NFS / MITM / no padding.
  2. Why must \(p\) and \(q\) be large and not too close (Fermat factoring intuition)?
  3. Parameter literacy: roughly how many decimal digits is a \(2048\)-bit integer? (Use \(\log_{10}2\approx 0.301\).)
  4. List three things a production system needs beyond textbook RSA math.
  5. One paragraph: what hardness assumption underlies RSA confidentiality in the textbook model?

E. Stretch

  1. Prove RSA correctness via CRT: show \(m^{ed}\equiv m\pmod p\) and mod \(q\) when \(n=pq\), \(ed\equiv 1\pmod{\varphi(n)}\).
  2. Compute a full successive-squaring table for \(13^{27}\bmod 55\) from Example 3.
  3. Compare DH shared secret computation count (two exponentiations per party after receipt) vs RSA encrypt (one exp).
  4. If \(\varphi(n)\) is leaked but not \(p,q\), is recovering \(d\) from \(e\) easy? What about factoring from \(\varphi(n)\)?
  5. Write a half-page “threat model” paragraph separating math hardness from protocol/authentication/side channels.

Deep dive — RSA correctness via CRT (full sketch)

Let \(n=pq\), \(ed=1+t\varphi(n)=1+t(p-1)(q-1)\). Need \(m^{ed}\equiv m\pmod p\) and \(\pmod q\).

Mod \(p\): If \(p\mid m\) then both sides \(0\). If \(p\nmid m\), Fermat: \(m^{p-1}\equiv 1\pmod p\), so \[ m^{ed}=m\cdot m^{t(p-1)(q-1)}=m\cdot (m^{p-1})^{t(q-1)}\equiv m\cdot 1\equiv m\pmod p. \] Similarly mod \(q\). By CRT (since \(p,q\) coprime), \(m^{ed}\equiv m\pmod{n}\).

This removes the \(\gcd(m,n)=1\) hypothesis needed for the pure Euler argument.

Deep dive — what “hardness” means in this volume

Phrase Meaning here
“Believed hard” No efficient classical algorithm known for general large instances; not a theorem that none exists
“Toy breakable” Brute force / factoring by hand works
“Parameter literacy” Orders of magnitude for real moduli; not a security proof
“Attack name awareness” Recognize the failure mode in prose; no exploit development

Additional worked examples

Example 9 — Full tiny RSA cycle.
\(p=3,q=11,n=33,\varphi=20\). \(e=3\), \(d=7\) because \(21\equiv 1\pmod{20}\).
\(m=4\): \(c=4^3=64\equiv 31\pmod{33}\). Decrypt \(31^7\bmod 33\).
\(31\equiv -2\), \((-2)^7=-128\equiv -128+4\cdot 33=-128+132=4\pmod{33}\). ✓

Example 10 — DH shared secret equality.
Always \((g^b)^a=g^{ba}=g^{ab}=(g^a)^b\) in any abelian exponent arithmetic — the group is multiplicative mod \(p\).

Example 11 — Bad \(e\).
\(\varphi=20\), \(e=5\): \(\gcd(5,20)=5\neq 1\), inverse fails.

Example 12 — Public vs private.
Publishing \(n,e\) is intended. Publishing \(\varphi(n)\) essentially reveals factoring (solve for \(p,q\) from \(n\) and \(\varphi=(p-1)(q-1)\)).

Example 13 — Digit count.
\(2048\) bits: \(2048\cdot\log_{10}2\approx 2048\cdot 0.3010\approx 616\) decimal digits.

Example 14 — Dictionary attack on textbook RSA.
If \(m\) is a short PIN \(0000\)–\(9999\), attacker computes \(c'=m^e\bmod n\) for all PINs and compares to \(c\) — no factoring needed. Padding randomizes \(m\).

More exercises

  1. Keygen \(p=5,q=17\); choose \(e=3\) if valid; find \(d\); encrypt \(m=10\).
  2. Show recovering \(d\) from \(e,\varphi\) is extended Euclid.
  3. Explain why \(e=65537\) is popular (culture: high Hamming weight of \(2^{16}+1\) is \(2\) — fast public ops).
  4. DH with \(p=23,g=5,a=7,b=4\): compute \(A,B,K\).
  5. Given \(n=77\) and \(\varphi(n)=60\), factor \(n\) by solving quadratic for \(p,q\).
  6. List five things textbook RSA omits that TLS-class systems need (bullets).
  7. Write a half-page: “I will never implement RSA from this day for production because…”

Selected mini-solutions

  1. \(A=2^4=16\equiv 5\pmod{11}\), \(B=2^3=8\), \(K=8^4\bmod 11\) or \(5^3\bmod 11\).
  2. \(n=91\), \(\varphi=72\); e.g. \(e=5\), find \(d\) with \(5d\equiv 1\pmod{72}\).
  3. \(2048\cdot 0.301\approx 616\) digits.
  4. Successive squaring table for \(13^{27}\bmod 55\) should return \(7\).

Common pitfalls

Pitfall Fix
Thinking toy RSA is “educationally secure” Algebra ≠ security
Reducing exponents mod \(n\) Exponents reduce mod \(\varphi(n)\)
Implementing crypto from this chapter Use libraries and standards
Confusing DLP with factoring Different problems; both are assumptions
Forgetting authentication on DH Shared math key without identity binding
Leaking \(p,q\) or \(\varphi(n)\) Equivalent to breaking private key

Synthesis — DH/RSA literacy workout

S1. State DLP with all inputs/outputs; state CDH in one sentence.

S2. DH: \(p=19\), \(g=2\), \(a=5\), \(b=7\) — compute \(A,B,K\) (hand powering).

S3. RSA: \(p=7,q=19\); pick valid \(e\); find \(d\); encrypt \(m=5\).

S4. Prove Euler-form correctness \(m^{ed}\equiv m\pmod n\) when \(\gcd(m,n)=1\).

S5. Why is publishing \(\varphi(n)\) catastrophic?

S6. Match: Wiener / Hastad / MITM / no-padding — one-line each.

S7. Decimal digits in a \(3072\)-bit modulus (\(\log_{10}2\approx 0.3010\)).

S8. Write 6 sentences: boundary between this day’s algebra and production crypto engineering.

Checkpoint

  • Can run tiny DH and explain \(g^{ab}\)
  • Can keygen tiny RSA: \(n,e,d\) with \(ed\equiv 1\pmod{\varphi(n)}\)
  • Can encrypt/decrypt a toy message by hand
  • Can state DLP and RSA factoring assumptions
  • Knows attack names and parameter literacy orders of magnitude
  • Exercises A–D done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — RSA correctness checklist (both proofs)

Path A — Euler (needs \(\gcd(m,n)=1\)).
\(ed=1+t\varphi(n)\) ⇒ \(m^{ed}=m\cdot(m^{\varphi(n)})^t\equiv m\cdot 1\equiv m\pmod n\).

Path B — CRT (works for all \(m\)).
Prove \(m^{ed}\equiv m\pmod p\) and \(\pmod q\) separately via Fermat, then combine. This is the industrial-strength correctness story for textbook RSA math.

\(\lambda(n)\) note. Modern specs often use \(ed\equiv 1\pmod{\lambda(n)}\) with \(\lambda=\mathrm{lcm}(p-1,q-1)\mid\varphi(n)\). Same correctness; sometimes smaller \(d\). Awareness only.

Deeper theory — what the eavesdropper sees (DH)

Public transcript: \((p,g,A,B)=(p,g,g^a,g^b)\).
Passive adversary goals:

  1. Recover \(a\) or \(b\) (DLP).
  2. Recover \(K=g^{ab}\) without necessarily recovering \(a\) or \(b\) (CDH).
  3. Distinguish \(K\) from random (DDH — decision Diffie–Hellman; awareness).

Active adversary: can replace \(A\) or \(B\) (MITM) unless identities are bound by signatures/MACs — protocol layer, not pure algebra failure of \(g^{ab}=g^{ba}\).

Worked examples — complete toy cycles

Example 15 — Full DH with \(p=23\), \(g=5\), \(a=6\), \(b=5\).
\(A=5^6\equiv 8\pmod{23}\) (from earlier).
\(B=5^5=3125\bmod 23\): \(5^2\equiv 2\), \(5^4\equiv 4\), \(5^5\equiv 20\pmod{23}\).
Alice: \(K=B^a=20^6\bmod 23\). Bob: \(K=A^b=8^5\bmod 23\).
Compute \(20^2=400\equiv 9\pmod{23}\) (\(23\cdot 17=391\), \(400-391=9\)); continue carefully until both get the same \(K\). Equality is the check.

Example 16 — RSA full ladder \(n=55\), \(e=3\), \(d=27\), \(m=8\).
\(c=8^3=512\bmod 55\): \(55\cdot 9=495\), \(c=17\).
Decrypt \(17^{27}\bmod 55\) by successive squaring:
\(17^2=289\equiv 14\pmod{55}\) (\(55\cdot 5=275\), \(289-275=14\)),
\(17^4\equiv 14^2=196\equiv 31\), \(17^8\equiv 31^2=961\equiv 26\) (\(55\cdot 17=935\), \(961-935=26\)),
\(17^{16}\equiv 26^2=676\equiv 16\pmod{55}\) (\(55\cdot 12=660\)).
\(27=16+8+2+1\) ⇒ \(17^{27}\equiv 16\cdot 26\cdot 14\cdot 17\bmod 55\). Multiply step by step; result must be \(8\).

Example 17 — Factoring from \(\varphi\).
\(n=77\), \(\varphi=60\). Then \(p+q=n-\varphi+1=77-60+1=18\), \(pq=77\). Roots of \(t^2-18t+77=0\): \((t-7)(t-11)=0\). Factors \(7,11\).

Extra exercises — literacy with numbers

  1. DH: \(p=19\), \(g=2\), \(a=10\), \(b=3\) — compute \(A,B,K\).
  2. RSA: \(p=11\), \(q=13\), \(e=7\) — find \(d\); encrypt \(m=2\).
  3. Prove Path B correctness sketch mod \(p\) carefully for \(p\nmid m\) and \(p\mid m\).
  4. Show that if \(d\) is known and \(e,n\) public, recovering \(p,q\) is still not “immediate arithmetic” from \(d\) alone without more work — but leaking \(\varphi\) is enough (contrast).
  5. Parameter: how many bits in a number with \(100\) decimal digits? (Use \(\log_2 10\approx 3.322\).)
  6. List four production requirements beyond \(c=m^e\bmod n\).
  7. Explain malleability: given \(c=m^e\), attacker sends \(c'= (2^e)c\equiv (2m)^e\) — textbook RSA multiplies messages.
  8. Write a 8–10 sentence “I will use libraries because…” paragraph covering padding, side channels, parameter choice, and review.

Mini-solutions (selected)

  1. \(n=143\), \(\varphi=120\); \(7d\equiv 1\pmod{120}\) — extended Euclid for \(d\).
  2. \(100/\log_{10}2\approx 100/0.3010\approx 332\) bits.
  3. \((2m)^e=2^e m^e\equiv 2^e c\pmod n\).

Closing synthesis card

Story Algebra checkpoint
DH shared secret \(g^{ab}\) both ways
RSA \(d\) \(ed\equiv 1\pmod{\varphi(n)}\)
RSA decrypt \(m^{ed}\equiv m\pmod n\)
Hardness DLP / factoring assumptions
Practice Toy only; libraries in production

Tomorrow

Day 78 — Chinese Remainder Theorem.

Day 78 — Chinese Remainder Theorem

Stage VII · concept day
Goal: Solve systems \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) when \(\gcd(m,n)=1\); constructive proof; general pairwise coprime systems; non-coprime consistency; applications (secret sharing lite, calendars).

Why this matters

CRT is the structural theorem that \(\mathbb{Z}/mn\mathbb{Z}\cong\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}\) when \(m,n\) coprime. It speeds modular computations (RSA CRT decryption literacy), reconstructs integers from residues, and appears in scheduling and secret-sharing puzzles. Constructive CRT is also a clean inverse application.

Note

No labs. Hand solutions of small systems. No coding of big-integer CRT.

Theory

Two congruences, coprime moduli

Theorem (CRT, two equations). Let \(m,n>0\) with \(\gcd(m,n)=1\). For any integers \(a,b\), the system \[ \begin{cases} x\equiv a\pmod m\\ x\equiv b\pmod n \end{cases} \] has a solution, and the solution is unique modulo \(mn\).

Constructive proof / algorithm.

  1. Since \(\gcd(m,n)=1\), there exists \(m^{-1}\bmod n\), i.e. \(y\) with \(my\equiv 1\pmod n\).
  2. Set \[ x_0 = a + m\bigl((b-a)y\bmod n\bigr). \] More symmetrically: find \(u,v\) with \(mu+nv=1\) (Bézout). Then \[ x_0 = a\,nv + b\,mu \] satisfies both congruences because \(nv\equiv 1\pmod m\) and \(mu\equiv 1\pmod n\).
  3. Standard explicit form: \[ x = \sum_i a_i M_i y_i, \] for two moduli \(M=mn\), \(M_1=n\), \(M_2=m\), \(y_1\equiv M_1^{-1}\pmod m\), \(y_2\equiv M_2^{-1}\pmod n\), \(a_1=a\), \(a_2=b\): \[ x_0 = a\, n\, (n^{-1}\bmod m) + b\, m\, (m^{-1}\bmod n). \]
  4. General solution: \(x=x_0 + mnt\), \(t\in\mathbb{Z}\).

Verification. \(x_0\equiv a\cdot n\cdot n^{-1}\equiv a\pmod m\) (second term has factor \(m\)). Similarly mod \(n\).

Uniqueness

If \(x,x'\) both solve the system, then \(m\mid(x-x')\) and \(n\mid(x-x')\), so \(mn\mid(x-x')\) when \(\gcd(m,n)=1\).

General pairwise coprime system

Theorem. Let \(m_1,\ldots,m_k\) be pairwise coprime (\(\gcd(m_i,m_j)=1\) for \(i\neq j\)). Let \(M=\prod m_i\). The system \[ x\equiv a_i\pmod{m_i},\qquad i=1,\ldots,k \] has a unique solution modulo \(M\).

Construction. Let \(M_i=M/m_i\). Then \(\gcd(M_i,m_i)=1\); let \(y_i\equiv M_i^{-1}\pmod{m_i}\). Set \[ x_0=\sum_{i=1}^k a_i M_i y_i. \] Then \(x_0\equiv a_j\pmod{m_j}\) for each \(j\), and solutions are \(x_0+Mt\).

Non-coprime moduli

Theorem (consistency). The system \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) has a solution iff \[ a\equiv b\pmod{\gcd(m,n)}. \] If solvable, the solution is unique modulo \(\mathrm{lcm}(m,n)\).

Proof idea. Necessity: if \(x=a+mt=b+ns\), then \(a-b=ns-mt\), so \(\gcd(m,n)\mid(a-b)\). Sufficiency: divide through by \(d=\gcd(m,n)\) and apply coprime CRT to moduli \(m/d,n/d\) carefully, or solve \(a+mt\equiv b\pmod n\) as a linear congruence in \(t\).

Ring isomorphism literacy

When \(\gcd(m,n)=1\), the map \[ \mathbb{Z}/mn\mathbb{Z}\to \mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z},\qquad x\bmod mn\mapsto (x\bmod m,\, x\bmod n) \] is a ring isomorphism. CRT is surjectivity + injectivity of this map.

Applications

Calendar / scheduling. “\(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\), \(x\equiv 2\pmod 7\)” — classic Sun Tzu problem style; \(M=105\).

Secret sharing lite (idea). A secret \(s\) in a range can be packaged as residues mod coprime moduli; enough residues reconstruct \(s\) via CRT if \(s<M\). (Real secret sharing uses Shamir polynomials — awareness; this is only the residue-reconstruction idea.)

RSA CRT decryption (literacy). Compute \(c^d\bmod p\) and \(c^d\bmod q\) separately, recombine via CRT — faster exponentiation in practice. No implementation today.

Simultaneous range constraints. Finding \(n\) with given remainders (e.g. packing, cyclic scheduling).

Worked examples

Example 1 — Classic two-modulus.
Solve \(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\).
\(M=15\), \(M_1=5\), \(y_1\equiv 5^{-1}\equiv 2\pmod 3\) (\(5\equiv 2\), \(2\cdot 2=4\equiv 1\)).
\(M_2=3\), \(y_2\equiv 3^{-1}\equiv 2\pmod 5\) (\(3\cdot 2=6\equiv 1\)).
\(x_0=2\cdot 5\cdot 2 + 3\cdot 3\cdot 2=20+18=38\equiv 8\pmod{15}\).
Check: \(8\equiv 2\pmod 3\), \(8\equiv 3\pmod 5\). ✓

Example 2 — Bézout form.
\(3u+5v=1\): \(u=2\), \(v=-1\). Then \(x=a\cdot 5\cdot(-1)?\) Wait — use \(x=a(1-3u)+b(3u)\) carefully… Prefer the standard sum form to avoid sign errors; verify by substitution.

Example 3 — Three moduli.
\(x\equiv 1\pmod 2\), \(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\).
\(M=30\), \(M_1=15\), \(M_2=10\), \(M_3=6\).
\(y_1\equiv 15^{-1}\equiv 1^{-1}\equiv 1\pmod 2\).
\(y_2\equiv 10^{-1}\equiv 1^{-1}\equiv 1\pmod 3\).
\(y_3\equiv 6^{-1}\equiv 1^{-1}\equiv 1\pmod 5\).
\(x_0=1\cdot 15\cdot 1 + 2\cdot 10\cdot 1 + 3\cdot 6\cdot 1=15+20+18=53\equiv 23\pmod{30}\).
Check: \(23\) odd; \(23\equiv 2\pmod 3\); \(23\equiv 3\pmod 5\). ✓

Example 4 — Non-coprime solvable.
\(x\equiv 4\pmod 6\), \(x\equiv 10\pmod{15}\). \(\gcd(6,15)=3\), \(4\equiv 1\), \(10\equiv 1\pmod 3\) — consistent.
Solutions mod \(\mathrm{lcm}(6,15)=30\). Try: \(x=10\) works? \(10\equiv 4\pmod 6\)? \(10-4=6\) yes; \(10\equiv 10\pmod{15}\). So \(x\equiv 10\pmod{30}\).

Example 5 — Non-coprime impossible.
\(x\equiv 1\pmod 6\), \(x\equiv 2\pmod{15}\). \(1\not\equiv 2\pmod 3\). No solution.

Example 6 — Linear congruence via CRT idea.
Solve \(x\equiv 3\pmod 4\), \(x\equiv 5\pmod 7\). \(M=28\).
\(x=3+4t\equiv 5\pmod 7\) ⇒ \(4t\equiv 2\pmod 7\). Multiply by inverse of \(4\) mod \(7\) (\(4\cdot 2=8\equiv 1\), inv \(=2\)): \(t\equiv 4\pmod 7\). \(t=4+7s\), \(x=3+4(4+7s)=19+28s\).

Example 7 — Counting solutions.
Number of residue classes mod \(30\) satisfying \(x\equiv 1\pmod 2\) and \(x\equiv 1\pmod 3\): equivalent to \(x\equiv 1\pmod 6\), so \(30/6=5\) classes mod \(30\).

Example 8 — Calendar.
\(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\), \(x\equiv 2\pmod 7\).
Note first and third: \(x\equiv 2\pmod{21}\) if CRT on \(3,7\) (coprime). Then \(x=2+21k\equiv 3\pmod 5\) ⇒ \(21k\equiv 1\pmod 5\) ⇒ \(k\equiv 1\pmod 5\) because \(21\equiv 1\). \(k=1+5t\), \(x=23+105t\). Classic answer \(23\) mod \(105\).

Exercises

A. Two coprime moduli

  1. Solve \(x\equiv 1\pmod 4\), \(x\equiv 2\pmod 5\).
  2. Solve \(x\equiv 3\pmod 5\), \(x\equiv 2\pmod 7\).
  3. Solve \(x\equiv 0\pmod 4\), \(x\equiv 1\pmod 9\).
  4. Prove uniqueness mod \(mn\) when \(\gcd(m,n)=1\).
  5. Find \(x\) with \(x\equiv -1\pmod{11}\), \(x\equiv -1\pmod{13}\). Interpret.

B. Construction details

  1. For moduli \(8\) and \(9\), compute \(M_i\), \(y_i\) and solve \(x\equiv 3\pmod 8\), \(x\equiv 5\pmod 9\).
  2. Solve using the method of successive substitution (Example 6 style): \(x\equiv 4\pmod 7\), \(x\equiv 3\pmod{10}\).
  3. Verify that \(x_0=\sum a_i M_i y_i\) satisfies \(x_0\equiv a_j\pmod{m_j}\) in general (write the argument).
  4. Find the inverse of \(M_1=15\) mod \(m_1=4\) for a \(2\cdot 3\cdot 5\) style system with first modulus \(4\) — wait, use \(m_1=4,m_2=3,m_3=5\) and \(a_i=1\) all; solve \(x\equiv 1\pmod{60}\)? Actually \(x\equiv 1\) mod each means \(x\equiv 1\pmod{60}\).

C. Three or more

  1. Solve \(x\equiv 1\pmod 3\), \(x\equiv 2\pmod 4\), \(x\equiv 3\pmod 5\).
  2. Solve \(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\), \(x\equiv 2\pmod 7\) (Example 8 without looking).
  3. How many solutions mod \(210\) to \(x\equiv 1\pmod 2\), \(x\equiv 1\pmod 3\), \(x\equiv 1\pmod 5\), \(x\equiv 1\pmod 7\)?

D. Non-coprime

  1. Determine solvability: \(x\equiv 7\pmod{12}\), \(x\equiv 11\pmod{18}\).
  2. Same: \(x\equiv 7\pmod{12}\), \(x\equiv 13\pmod{18}\).
  3. Solve (if possible) \(x\equiv 6\pmod{10}\), \(x\equiv 16\pmod{15}\).
  4. Prove necessity of \(a\equiv b\pmod{\gcd(m,n)}\).
  5. State the uniqueness modulus when solvable.

E. Applications and stretch

  1. Secret sharing lite: moduli \(5,7,8\) (pairwise coprime), secret \(s=13\). Publish \(s\bmod 5\), \(s\bmod 7\), \(s\bmod 8\). Reconstruct via CRT.
  2. Scheduling: a task every \(6\) days on residue \(1\), and another constraint every \(7\) days on residue \(3\) — find day numbers.
  3. RSA literacy: explain in 4–6 sentences why decrypting mod \(p\) and mod \(q\) then CRT is equivalent to decrypting mod \(n\).
  4. Prove the ring map \(\mathbb{Z}/mn\mathbb{Z}\to\mathbb{Z}/m\times\mathbb{Z}/n\) is injective when \(\gcd(m,n)=1\).
  5. Stretch: solve \(x\equiv 3\pmod 4\), \(x\equiv 5\pmod 6\) after checking consistency.
  6. Stretch: general system \(x\equiv a_i\pmod{m_i}\) not pairwise coprime — outline a strategy using lcm and successive equations.

Deep dive — algorithm card (pairwise coprime)

Input: (a_i, m_i) for i=1..k, pairwise coprime m_i
M ← product of all m_i
for each i:
    M_i ← M / m_i
    y_i ← inverse of M_i modulo m_i   // extended Euclid
x0 ← sum_i a_i * M_i * y_i
return x0 mod M

Complexity literacy. \(k\) inverses of size related to \(m_i\); for hand work \(k\le 4\) and small moduli.

Deep dive — non-coprime solver

To solve \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) when \(d=\gcd(m,n)\mid(a-b)\):

  1. Write \(x=a+mt\).
  2. \(a+mt\equiv b\pmod n\) ⇒ \(mt\equiv b-a\pmod n\).
  3. Divide equation and modulus by \(d\): \((m/d)t\equiv (b-a)/d\pmod{n/d}\).
  4. Invert \(m/d\) mod \(n/d\) (now coprime), solve for \(t\), substitute.
  5. Solutions unique mod \(\mathrm{lcm}(m,n)=mn/d\).

Additional worked examples

Example 9 — Four moduli.
\(x\equiv 1\pmod 2\), \(x\equiv 1\pmod 3\), \(x\equiv 1\pmod 5\), \(x\equiv 1\pmod 7\) ⇒ \(x\equiv 1\pmod{210}\).

Example 10 — Successive substitution.
\(x\equiv 2\pmod 5\), \(x\equiv 3\pmod 7\), \(x\equiv 2\pmod 3\).
From first: \(x=5s+2\). Into second: \(5s+2\equiv 3\pmod 7\) ⇒ \(5s\equiv 1\pmod 7\). Inv of \(5\) mod \(7\) is \(3\): \(s\equiv 3\pmod 7\), \(s=7t+3\), \(x=35t+17\).
Into third: \(35t+17\equiv 2\pmod 3\) ⇒ \(2t+2\equiv 2\pmod 3\) ⇒ \(2t\equiv 0\pmod 3\) ⇒ \(t\equiv 0\pmod 3\).
\(t=3u\), \(x=105u+17\). Check: \(17\bmod 5=2\), \(17\bmod 7=3\), \(17\bmod 3=2\).

Example 11 — Isomorphism count.
Number of pairs \((u\bmod m,v\bmod n)\) is \(mn\); number of classes mod \(mn\) is \(mn\) — bijection when coprime.

Example 12 — Inconsistent.
\(x\equiv 1\pmod 4\), \(x\equiv 0\pmod 6\): \(\gcd(4,6)=2\), \(1\not\equiv 0\pmod 2\). Impossible.

Example 13 — RSA CRT decrypt literacy.
\(d_p=d\bmod(p-1)\), compute \(m_p=c^{d_p}\bmod p\), \(m_q=c^{d_q}\bmod q\), recombine — same \(m\) as \(c^d\bmod n\), fewer bit operations for large \(n\).

More exercises

  1. Solve \(x\equiv 4\pmod 7\), \(x\equiv 5\pmod 8\), \(x\equiv 6\pmod 9\).
  2. Prove: if \(x\equiv a\pmod m\) and \(x\equiv a\pmod n\) and \(\gcd(m,n)=1\) then \(x\equiv a\pmod{mn}\).
  3. Find all \(x\bmod 60\) with \(x\equiv 3\pmod 4\) and \(x\equiv 5\pmod 3\).
  4. Secret sharing lite: residues \(s\equiv 2\pmod 5\), \(s\equiv 3\pmod 7\), \(s\equiv 2\pmod 8\); reconstruct \(s\bmod 280\).
  5. For \(m=12,n=18\), characterize all \((a,b)\) for which the system is solvable.
  6. CS: two cyclic timers period \(12\) and \(35\); when do they fire together if offsets given?
  7. Verify Example 10’s answer \(17\) mod \(105\).

Selected mini-solutions

  1. \(x\equiv 6\pmod{20}\) (check: \(6\equiv 1\pmod 4?\) wait \(6\equiv 2\) — recompute: \(x=4k+1\equiv 2\pmod 5\) ⇒ \(4k\equiv 1\pmod 5\), inv \(4\) is \(4\), \(k\equiv 4\), \(x=17\equiv 17\pmod{20}\)).
  2. \(x\equiv -1\pmod{143}\).
  3. Check \(5\equiv 11\pmod 3\)? \(5\equiv 2\), \(11\equiv 2\) yes; solve carefully.
  4. \(s=13\): residues \(3,6,5\); CRT reconstructs \(13\).

Common pitfalls

Pitfall Fix
Applying coprime formula when \(\gcd>1\) Check consistency first
Forgetting to reduce \(y_i=M_i^{-1}\bmod m_i\) Inverse is mod \(m_i\), not mod \(M\)
Uniqueness mod \(m\) or \(n\) only Uniqueness mod product (coprime case)
Arithmetic errors in \(M_i y_i\) Verify each congruence at the end
Pairwise vs overall coprimality Need pairwise for standard product theorem
Skipping verification Always plug back

Study notes — CRT decision tree

Two congruences x≡a (mod m), x≡b (mod n):
  d = gcd(m,n)
  if d does not divide (a-b): impossible
  if d = 1: unique mod mn; construct via M_i y_i
  if d > 1: unique mod lcm(m,n)=mn/d; use successive substitution
k pairwise coprime moduli: unique mod product; standard sum formula

Synthesis — CRT workout

S1. Solve \(x\equiv 3\pmod 8\), \(x\equiv 5\pmod 9\) by the formula; verify.

S2. Solve \(x\equiv 1\pmod 5\), \(x\equiv 2\pmod 6\), \(x\equiv 3\pmod 7\).

S3. Prove uniqueness mod \(mn\) when \(\gcd(m,n)=1\).

S4. Decide solvability of \(x\equiv 4\pmod{15}\), \(x\equiv 10\pmod{21}\); if yes, solve.

S5. Show \(x\equiv a\pmod m\) and \(x\equiv a\pmod n\) with coprime \(m,n\) ⇒ \(x\equiv a\pmod{mn}\).

S6. Secret sharing lite: reconstruct from \(s\equiv 1\pmod 4\), \(s\equiv 2\pmod 5\), \(s\equiv 3\pmod 7\).

S7. RSA CRT decrypt: explain equivalence in 5 sentences.

S8. Successive substitution on \(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\), \(x\equiv 2\pmod 7\).

Checkpoint

  • Can solve two-congruence CRT constructively
  • Can run the general pairwise formula
  • Can test non-coprime consistency
  • Can prove uniqueness mod \(mn\) when coprime
  • Can narrate one application (calendar / RSA CRT / residues)
  • Exercises A–D done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — isomorphism view (why CRT is structural)

Map. \(\Psi:\mathbb{Z}/mn\mathbb{Z}\to\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}\), \(\Psi([x]_{mn})=([x]_m,[x]_n)\).

Homomorphism. \(\Psi([x]+[y])=\Psi([x])+\Psi([y])\) and similarly for products — immediate from compatibility of congruences.

Injective when \(\gcd(m,n)=1\). If \(\Psi([x])=(0,0)\) then \(m\mid x\) and \(n\mid x\), so \(mn\mid x\) (coprime moduli). Kernel trivial.

Surjective. CRT existence: every pair \((a\bmod m,b\bmod n)\) is hit.

Moral. Solving systems is computing the inverse map \(\Psi^{-1}\). The formula \(x=\sum a_i M_i y_i\) is an explicit inverse.

Deeper theory — successive substitution always

Even for pairwise coprime systems, successive substitution is often less error-prone by hand than the big sum:

  1. Solve the first two congruences → one congruence mod \(m_1 m_2\).
  2. Incorporate the third mod \(m_3\), and so on.
  3. Verify at the end against every original congruence.

For non-coprime pairs, successive substitution plus the consistency check is the standard path.

Worked examples — more systems

Example 14 — \(x\equiv 3\pmod 8\), \(x\equiv 5\pmod 9\).
\(M=72\), \(M_1=9\), \(y_1\equiv 9^{-1}\equiv 1^{-1}\equiv 1\pmod 8\).
\(M_2=8\), \(y_2\equiv 8^{-1}\equiv (-1)^{-1}\equiv -1\equiv 8\pmod 9\)? \(8\cdot 8=64\equiv 1\pmod 9\) yes.
\(x_0=3\cdot 9\cdot 1+5\cdot 8\cdot 8=27+320=347\equiv 347-4\cdot 72=347-288=59\pmod{72}\).
Check: \(59\equiv 3\pmod 8\) (\(56+3\)), \(59\equiv 5\pmod 9\) (\(6\cdot 9=54\), rem \(5\)). ✓

Example 15 — Three moduli.
\(x\equiv 1\pmod 3\), \(x\equiv 2\pmod 4\), \(x\equiv 3\pmod 5\).
\(x=3t+1\equiv 2\pmod 4\) ⇒ \(3t\equiv 1\pmod 4\), inv of \(3\) is \(3\), \(t\equiv 3\pmod 4\), \(t=4s+3\), \(x=12s+10\).
\(12s+10\equiv 3\pmod 5\) ⇒ \(2s+0\equiv 3\pmod 5\) (\(10\equiv 0\)), \(2s\equiv 3\), inv of \(2\) is \(3\), \(s\equiv 9\equiv 4\pmod 5\).
\(s=5u+4\), \(x=12(5u+4)+10=60u+58\). So \(x\equiv 58\pmod{60}\).
Check: \(58\equiv 1\pmod 3\), \(58\equiv 2\pmod 4\), \(58\equiv 3\pmod 5\). ✓

Example 16 — Non-coprime solvable.
\(x\equiv 7\pmod{12}\), \(x\equiv 11\pmod{18}\). \(\gcd=6\), \(7\equiv 1\), \(11\equiv 5\pmod 6\) — inconsistent? \(1\not\equiv 5\). No solution.
Repair the exercise habit: always compute \(a-b\bmod d\) first. For \(x\equiv 7\pmod{12}\), \(x\equiv 13\pmod{18}\): \(7\equiv 1\), \(13\equiv 1\pmod 6\) — OK. Solve via \(x=12t+7\equiv 13\pmod{18}\) ⇒ \(12t\equiv 6\pmod{18}\). Divide by \(6\): \(2t\equiv 1\pmod 3\). Inv of \(2\) mod \(3\) is \(2\), \(t\equiv 2\pmod 3\), \(t=3s+2\), \(x=36s+31\). Mod \(\mathrm{lcm}(12,18)=36\).

Extra exercises — CRT drills

  1. Solve \(x\equiv 5\pmod 7\), \(x\equiv 3\pmod 8\).
  2. Solve \(x\equiv 2\pmod 5\), \(x\equiv 3\pmod 6\), \(x\equiv 4\pmod 7\).
  3. Prove injectivity of \(\Psi\) when \(\gcd(m,n)=1\).
  4. Characterize solvability for moduli \(10\) and \(15\).
  5. Reconstruct \(s\) from \(s\equiv 4\pmod 7\), \(s\equiv 1\pmod 8\), \(s\equiv 2\pmod 9\).
  6. Show \(x\equiv -1\pmod m\) and \(x\equiv -1\pmod n\) coprime ⇒ \(x\equiv -1\pmod{mn}\).
  7. RSA CRT literacy: write the three-line algorithm \(m_p,m_q\to m\bmod n\).
  8. Scheduling: \(x\equiv 0\pmod{12}\) and \(x\equiv 5\pmod{35}\) — solve or prove impossible.

Mini-solutions (selected)

  1. \(x=7k+5\equiv 3\pmod 8\) ⇒ \(7k\equiv -2\equiv 6\pmod 8\) ⇒ \(-k\equiv 6\) ⇒ \(k\equiv 2\pmod 8\) (since \(7\equiv -1\)); \(x=14+56t\equiv 14\pmod{56}\).
  2. Special case of “same residue mod each” ⇒ residue mod product.
  3. \(\gcd(12,35)=1\) always solvable; construct via formula.

Closing synthesis card

Task Method
Two coprime \(M_i y_i\) sum or substitution
\(k\) pairwise product modulus
Non-coprime \(d\mid(a-b)\); mod lcm
Verify plug into every congruence
Structure ring isomorphism literacy

Tomorrow

Day 79 — RNGs, LCGs, and randomness literacy.

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).

Day 80 — Gate VII (Number theory for CS)

Stage VII · gate day
Goal: Demonstrate integrated literacy: Euclid + extended Euclid, modular inverses, Fermat/Euler reduction, small CRT, RSA parameter identification, hash collision estimates, and one divisibility proof — without labs.

Why this matters

Stage VII tools reappear in the capstone (modular computation + inverse) and in every later systems discussion of hashing, modular reduction, and public-key stories. This gate certifies calculation fluency and short proof control under mild time pressure.

Important

No labs. Written mathematics only. Calculator only after a hand solution exists, and only for arithmetic check.

How to take this gate

  1. Timebox 100–140 minutes optional but recommended.
  2. Closed notes first pass; open notes only for remediation.
  3. Show all Euclid tables / inverse checks.
  4. Score with the rubric; remediate any section below \(50\%\) of its points.
  5. Log errors in a personal error file (congruence mistakes, inverse signs, CRT verification).

Rubric

Section Points Pass bar
A Divisibility & Euclid 20 ≥ 14
B Inverses & linear congruences 20 ≥ 14
C Fermat / Euler reduction 15 ≥ 10
D CRT 15 ≥ 10
E Hashing + crypto literacy 15 ≥ 10
F Proof + mixed 15 ≥ 10
Total 100 ≥ 75, no section \(<50\%\)

Section A — Divisibility & Euclid (20)

  1. (3) Write the definition of \(a\mid b\). Prove: if \(a\mid b\) and \(a\mid c\) then \(a\mid(bx+cy)\) for all integers \(x,y\).
  2. (3) Compute \(\gcd(1230,348)\) by Euclid; show every step.
  3. (4) Find integers \(x,y\) with \(1230x+348y=\gcd(1230,348)\).
  4. (3) State Euclid’s lemma. Prove it using Bézout (short).
  5. (3) Factor \(360\) completely; compute \(\gcd(360,252)\) and \(\mathrm{lcm}(360,252)\) via FTA or Euclid+identity.
  6. (4) Solve \(348x+1230y=18\) or show impossible. If possible, give the general solution.

Section B — Inverses & linear congruences (20)

  1. (3) For which \(a\in\{0,1,\ldots,14\}\) does \(a^{-1}\bmod 15\) exist? List them.
  2. (4) Compute \(11^{-1}\bmod 26\) by extended Euclid; verify.
  3. (4) Solve \(11x\equiv 15\pmod{26}\).
  4. (4) Solve \(6x\equiv 9\pmod{15}\); list all incongruent solutions.
  5. (3) Prove: if \(ax\equiv 1\pmod n\) then \(\gcd(a,n)=1\).
  6. (2) State Wilson’s theorem. Verify for \(p=7\).

Section C — Fermat / Euler (15)

  1. (3) Compute \(\varphi(36)\) and \(\varphi(100)\).
  2. (4) Compute \(3^{100}\bmod 7\) using Fermat.
  3. (4) Compute \(7^{123}\bmod 10\) using Euler.
  4. (4) Find \(\mathrm{ord}_7(3)\) (smallest \(k>0\) with \(3^k\equiv 1\pmod 7\)). Confirm it divides \(\varphi(7)\).

Section D — CRT (15)

  1. (5) Solve \(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\). Give all solutions.
  2. (5) Solve \(x\equiv 1\pmod 4\), \(x\equiv 2\pmod 5\), \(x\equiv 3\pmod 7\).
  3. (5) Does \(x\equiv 5\pmod{12}\), \(x\equiv 11\pmod{18}\) have a solution? Justify with the consistency criterion; if yes, find the general solution.

Section E — Hashing + crypto literacy (15)

  1. (3) Under uniform independent hashing of \(n=30\) keys into \(m=200\) buckets, compute expected number of colliding pairs \(\binom{n}{2}/m\).
  2. (3) Birthday literacy: about how large must \(n\) be for collisions to become likely when \(m=10^4\)? (Order \(\sqrt{m}\) with a numerical estimate.)
  3. (3) RSA toy: \(p=5\), \(q=13\), \(n=65\), \(\varphi=48\). Is \(e=5\) a valid public exponent? If yes, find \(d\) with \(ed\equiv 1\pmod{48}\).
  4. (3) DH: with public \(p,g\), Alice sends \(g^a\bmod p\), Bob \(g^b\bmod p\). What do they compute as shared secret? What problem should an eavesdropper not solve easily?
  5. (3) Name two reasons textbook RSA (\(c=m^e\bmod n\) with no padding) is not production encryption (literacy bullets).

Section F — Proof + mixed (15)

  1. (5) Prove one of the following carefully (full sentences):
      1. If \(p\) is prime and \(p\mid n^2\) then \(p\mid n\).
      1. There are infinitely many primes (Euclid).
      1. If \(\gcd(a,n)=1\) then \(a\) has an inverse mod \(n\) (existence via Bézout).
  2. (5) LCG literacy: state Hull–Dobell’s three conditions. For \(m=8\), \(a=5\), \(c=3\), does full period hold? (Yes/no + which conditions.)
  3. (5) Mixed computation: find \(17^{-1}\bmod 100\), then solve the CRT system \(x\equiv 17^{-1}\pmod{4}\) wait — simpler: compute \(y=17^{-1}\bmod 100\), then find \(z\) with \(z\equiv y\pmod{100}\) and \(z\equiv 3\pmod 7\) (optional if time: at least compute \(y\) and set up the second congruence).
    Alternate 27 (cleaner): Compute \(5^{30}\bmod 13\) and \(x\) solving \(x\equiv 4\pmod 7\), \(x\equiv 3\pmod{13}\).

Capstone bridge (required reflection, unscored but mandatory)

Write 5–10 lines:

  • Which Stage VII skill is strongest / weakest?
  • Which modular computation will you use in the Day 88–90 dossier? (State a concrete problem idea: inverse, CRT, or Fermat reduction.)
  • One proof from this stage worth reusing as a capstone proof candidate?

Remediation map

Weak section Return to
A Days 71–72
B Days 73–74
C Day 75
D Day 78
E Days 76–77, 79
F Days 71, 74, 79

Re-test only weak sections after targeted practice; full gate retake if total \(<75\).

Self-score sheet

Section Score Notes / errors
A /20
B /20
C /15
D /15
E /15
F /15
Total /100

Pass? Y/N. Retake plan: …

Selected answer sketches (check only after attempting)

Use as verification, not as a first look.

  1. \(\gcd(1230,348)\): \(1230=3\cdot 348+186\); \(348=1\cdot 186+162\); \(186=1\cdot 162+24\); \(162=6\cdot 24+18\); \(24=1\cdot 18+6\); \(18=3\cdot 6+0\) ⇒ \(\gcd=6\).
  2. Extended Euclid on \((11,26)\) should yield inverse \(19\) because \(11\cdot 19=209=8\cdot 26+1\).
  3. \(\gcd(6,15)=3\mid 9\); solutions \(x\equiv 4,9,14\pmod{15}\) (verify).
  4. \(3^6\equiv 1\pmod 7\), \(100\equiv 4\pmod 6\) ⇒ \(3^{100}\equiv 3^4\equiv 81\equiv 4\pmod 7\).
  5. \(x\equiv 8\pmod{15}\).
  6. \(\gcd(5,48)=1\); find \(d\) with \(5d\equiv 1\pmod{48}\) (e.g. \(d=29\) since \(145=3\cdot 48+1\)).

If your answers differ, recompute before assuming the sketch is wrong — then compare carefully.

Common gate failures

Failure Fix
Inverse with wrong sign Always verify \(ax\equiv 1\)
Euler without coprimality Check \(\gcd(a,n)=1\)
CRT no verification Plug \(x\) into each congruence
RSA \(d\) mod \(n\) \(ed\equiv 1\pmod{\varphi(n)}\)
Birthday \(n=m\) Use \(\sqrt{m}\) scale
Proof by example General \(k\) in \(b=ak\)
Diophantine without \(d\mid c\) check Always test divisibility first

Extended answer sketches (second pass only)

3. From gcd steps for \((1230,348)\) ending at \(6\), back-substitute to \(1230x+348y=6\).
6. Scale the Bézout identity for \(6\) by \(3\) to reach \(18\); general solution uses \(\pm 348/6\) and \(\mp 1230/6\).
9. \(x\equiv 15\cdot 19\equiv 285\equiv 25\pmod{26}\) if inv is \(19\); verify \(11\cdot 25=275=10\cdot 26+15\).
15. \(7^4\equiv 1\pmod{10}\) cycle; \(123\bmod 4=3\) ⇒ \(7^{123}\equiv 7^3\equiv 3\pmod{10}\).
18. Use \(M=140\), compute \(M_i,y_i\) carefully; verify three ways.
20. \(\binom{30}{2}/200=435/200=2.175\).
21. \(\sqrt{10^4}=100\) order; refined \(\approx 1.2\cdot 100\approx 120\).
27 alt. \(5^{12}\equiv 1\pmod{13}\), \(30=2\cdot 12+6\), reduce; CRT: \(x=7k+4\equiv 3\pmod{13}\) ⇒ solve for \(k\).

Timing and strategy notes

Time left Priority
First 20 min A+B calculation accuracy
Next 25 min C+D (reduction + CRT)
Next 20 min E literacy full sentences
Next 25 min F proof quality
Last 10–15 Checks: multiply inverses, plug CRT

Partial credit maxims: write gcd steps even if stuck on coefficients; state Wilson even if pairing incomplete; give \(\sqrt{m}\) even if constant fuzzy.

Error log template (copy)

Item #: 
Wrong step:
Correct step:
Root cause (cancel / sign / φ / gcd / other):
Drill: 3 similar problems from Day __

Capstone modular item bank (choose one tonight)

  1. Inverse of \(23\) mod \(100\) + solve \(23x\equiv 7\pmod{100}\).
  2. CRT: \(x\equiv 3\pmod 8\), \(x\equiv 5\pmod 9\), \(x\equiv 2\pmod 5\).
  3. Compute \(3^{100}\bmod 7\) and \(3^{100}\bmod 13\), combine via CRT for mod \(91\).
  4. Full Euclid+Bézout on \((252,198)\) and interpret as inverse prep.

Record choice: ________

Optional oral mini-defense (5 min)

  1. State Euclid’s lemma + one-line Bézout proof idea.
  2. Why \(\varphi(15)=8\)? List units.
  3. What is wrong with “RSA is \(m^e\bmod n\) in production”?
  4. Birthday: why \(\sqrt{m}\) not \(m\)?

Stage VII formula sheet (memory side)

Topic Key fact
Divisibility \(a\mid b\Leftrightarrow \exists k,\ b=ak\); linear combinations
Euclid \(\gcd(a,b)=\gcd(b,a\bmod b)\); \(O(\log n)\) steps
Bézout \(\exists x,y:\ ax+by=\gcd\)
Inverse exists iff \(\gcd(a,n)=1\)
Fermat \(a^{p-1}\equiv 1\pmod p\) (\(p\nmid a\))
Euler \(a^{\varphi(n)}\equiv 1\pmod n\) (\(\gcd=1\))
CRT coprime moduli ⇒ unique mod product
Birthday collisions at \(\Theta(\sqrt{m})\)
RSA \(ed\equiv 1\pmod{\varphi(n)}\); \(m^{ed}\equiv m\pmod n\)
Wilson \((p-1)!\equiv -1\pmod p\) iff \(p\) prime (\(p>1\))
LCG full period Hull–Dobell three conditions on \((m,a,c)\)
Order \(\mathrm{ord}_n(a)\mid\varphi(n)\) when \(\gcd(a,n)=1\)

Gate motto: every inverse is checked by multiplication; every CRT answer is plugged back.

Mixed practice set (if gate finished early / remediation)

M1. Euclid + inverse: \(\gcd(97,20)\), then \(20^{-1}\bmod 97\) if exists.

M2. \(5^{30}\bmod 11\) by Fermat.

M3. CRT: \(x\equiv 4\pmod 7\), \(x\equiv 3\pmod{11}\).

M4. Expected colliding pairs \(n=25\), \(m=200\).

M5. RSA: \(n=35\), \(\varphi=24\), \(e=5\) — find \(d\); encrypt \(m=4\).

M6. Prove: if \(a\mid bc\) and \(\gcd(a,b)=1\) then \(a\mid c\) (Gauss).

M7. Hull–Dobell: does \((m,a,c)=(12,5,1)\) have full period?

M8. Wilson verify \(p=11\) by pairing, not by expanding \(10!\).

M9. Order of \(5\) mod \(12\) if defined; if not, explain.

M10. Write one paragraph linking Bézout → inverse → RSA \(d\).

Checkpoint

  • Section A attempted closed-book
  • Section B inverses verified by multiplication
  • Section C exponent reductions shown with mod \(\varphi\) or \(p-1\)
  • Section D CRT solutions checked
  • Section E literacy answers written in full sentences
  • Section F proof in full sentences
  • Capstone modular item idea recorded
  • Error log updated; remediation scheduled if needed
  • Score ≥ 75 or retake plan dated
  • Mixed practice M1–M5 attempted if remediating

Two personal takeaways from Stage VII:

  1. …
  2. …

Full worked gate rehearsal (timed practice set)

Do this set closed-book in \(45\) minutes before the formal gate, then score.

R1. Euclid: \(\gcd(252,198)\); Bézout coefficients for the gcd.
R2. Inverse: \(23^{-1}\bmod 100\); solve \(23x\equiv 15\pmod{100}\).
R3. Fermat: \(2^{40}\bmod 13\).
R4. Euler: last digit of \(9^{123}\) (i.e. mod \(10\)).
R5. CRT: \(x\equiv 3\pmod 5\), \(x\equiv 4\pmod 7\).
R6. Hash: \(\mathbb{E}[\text{colliding pairs}]\) for \(n=40\), \(m=800\).
R7. RSA: \(p=5,q=17,e=3\) — is \(e\) valid? Find \(d\).
R8. Hull–Dobell: \((m,a,c)=(16,5,3)\) full period?
R9. Wilson: verify \(p=5\) and explain why \(n=9\) fails.
R10. Proof: if \(\gcd(a,n)=1\) then \(a\) has an inverse mod \(n\).

Rehearsal answer keys (second pass)

R1. \(252=1\cdot 198+54\); \(198=3\cdot 54+36\); \(54=1\cdot 36+18\); \(36=2\cdot 18+0\) ⇒ \(\gcd=18\). Back-sub for \(18=252x+198y\).
R2. Extended Euclid on \((23,100)\) → inverse \(87\) because \(23\cdot 87=2001=20\cdot 100+1\); \(x\equiv 15\cdot 87=1305\equiv 5\pmod{100}\).
R3. \(2^{12}\equiv 1\pmod{13}\), \(40=3\cdot 12+4\) ⇒ \(2^{40}\equiv 2^4=16\equiv 3\).
R4. \(9^1\equiv 9\), \(9^2\equiv 1\pmod{10}\) cycle \(2\); \(123\) odd ⇒ last digit \(9\).
R5. \(x=5k+3\equiv 4\pmod 7\) ⇒ \(5k\equiv 1\pmod 7\); inv of \(5\) is \(3\); \(k\equiv 3\); \(x\equiv 18\pmod{35}\).
R6. \(\binom{40}{2}/800=780/800=0.975\).
R7. \(n=85\), \(\varphi=64\), \(\gcd(3,64)=1\); \(3d\equiv 1\pmod{64}\) ⇒ \(d=43\) (\(129=2\cdot 64+1\)).
R8. \(\gcd(3,16)=1\); \(5\equiv 1\pmod 2\); \(5\equiv 1\pmod 4\) — yes.
R9. \(4!=24\equiv -1\pmod 5\); \(8!\equiv 0\pmod 9\).
R10. Bézout \(ax+ny=1\) ⇒ \(ax\equiv 1\pmod n\).

Proof quality rubric (Section F)

Level Description
0 Example only; no general argument
1 States theorem; major gap
2 Correct idea; missing quantifiers or case
3 Full sentences; cites Bézout/Euclid/Wilson correctly
4 Clean, reusable write-up (capstone quality)

Target level \(\ge 3\) on the chosen proof. Rewrite once if you score \(2\).

Stage VII integration map (capstone prep)

Capstone need Stage VII source day
Modular inverse 74
Exponent reduction 75
CRT recombination 78
Collision estimate 76
RSA parameter story 77
Randomness caveat 79
Divisibility lemmas 71–72

Pick one computational item and one short proof for the Day 88 outline tonight.

Final pre-gate checklist (10 minutes)

  • One Euclid table written from scratch
  • One inverse verified by multiplication
  • One CRT solution plugged back
  • One Fermat reduction with exponent mod \(p-1\)
  • One literacy paragraph (RSA or birthday) without notes
  • Error log has at least two historical mistakes recorded

If any box is unchecked, spend \(15\) minutes on that skill before scoring the formal gate.

Tomorrow

Day 81 — Big-O formally (Stage VIII begins).