Modular Arithmetic

RSA encrypts every message on the internet. The private key is d such that ed ≡ 1 (mod phi(n)). Computing d means finding the modular inverse in Z/phi(n)Z via the extended Euclidean algorithm. Every HTTPS connection, every credit card transaction, every password - held together by the operation a^{-1} mod n. The Euclidean algorithm (around 300 BCE) runs inside every browser on the planet.

• **RSA / ECDSA:** private key d computed as a modular inverse mod phi(n); Bitcoin transactions signed in Z/pZ over a 256-bit prime
• **SHA-256, MurmurHash:** chains of operations mod 2^32 and mod 2^64 as the avalanche mechanism inside hash functions; consistent hashing in distributed systems operates in the ring Z/n
• **RSA-CRT optimization:** four-fold decryption speedup by computing mod p and mod q separately, then reconstructing via CRT - built into OpenSSL
• **Shamir's secret sharing:** federated learning without a central server - secrets distributed via polynomial interpolation in Z/pZ

Sun Tzu and Counting an Army

The earliest statement of the Chinese Remainder Theorem appears in Sun Tzu's book (3rd-5th century CE): "An unknown number. Divided by three, remainder two; by five, remainder three; by seven, remainder two. What is the number?" Answer: twenty-three. According to legend, commanders counted troops by marching them in rows of three, five, and seven - and deduced the total from the remainders, without direct counting. Euler and Gauss formalized the method in the 18th-19th centuries.

Предварительные знания

• Euclidean Algorithm and GCD

Congruences and the Ring Z/nZ

RSA encrypts every message on the internet. The private key is d such that ed ≡ 1 (mod phi(n)). Every HTTPS connection, every credit card transaction, every password manager - all held together by the operation a^{-1} mod n. And that operation rests on one idea: two numbers that differ by a multiple of n are the same thing.

**Congruence:** a ≡ b (mod n) if and only if n divides (a - b), i.e., a and b leave the same remainder when divided by n. Examples: 17 ≡ 2 (mod 5), -3 ≡ 4 (mod 7), 100 ≡ 0 (mod 10) **Properties** - if a ≡ b and c ≡ d (mod n), then: - a + c ≡ b + d (mod n) - a * c ≡ b * d (mod n) - a^k ≡ b^k (mod n)

Hash functions do exactly the same. SHA-256 is a chain of operations mod 2^32 and mod 2^64: additions, bit shifts, constant tables. MurmurHash3 uses multiplications mod 2^32 as its avalanche mechanism. Consistent hashing in distributed systems operates in the ring Z/n, where n is the size of the virtual token space.

Congruences preserve addition and multiplication - but not division. 6 ≡ 0 (mod 6) and 3 ≡ 3 (mod 6), yet dividing both sides by 3 does not work directly: 2 is not congruent to 0 (mod 6). Division modulo n means multiplying by the modular inverse, and that inverse does not always exist.

Residue Classes and the Structure of Z/nZ

A residue class is not just a remainder - it is an infinite family of numbers: ..., -10, -3, 4, 11, 18, ... all leave remainder 4 when divided by 7. Modular arithmetic treats them as a single element. The finite set {0, 1, ..., n-1} with mod-n addition and multiplication is a new algebraic object: a ring.

**Ring of residues Z/nZ:** - Elements: {0, 1, 2, ..., n-1} - Addition: (a + b) mod n - Multiplication: (a * b) mod n - Additive identity: 0 - Multiplicative identity: 1 **Z/nZ is a field if and only if n is prime** (every non-zero element is invertible)

When n is prime, Z/pZ is the finite field GF(p). AES-256 operates in GF(2^8): each byte is a field element, ShiftRows and MixColumns are linear maps over it. Reed-Solomon codes (QR codes, CD, RAID-6) also rely on GF(2^8). Finite fields are not theoretical curiosities - they are the working mathematics inside every storage system.

The group of invertible elements Z/nZ* = {a : gcd(a, n) = 1}. Its order is Euler's totient phi(n). For a prime p: phi(p) = p - 1. For n = p*q: phi(n) = (p-1)(q-1). This formula is the heart of RSA.

Modular Inverse and the Extended Euclidean Algorithm

The number a^{-1} mod n is an x such that a*x ≡ 1 (mod n). It exists if and only if gcd(a, n) = 1 (Bezout's identity). The extended Euclidean algorithm finds it in O(log n) steps - and that is the exact routine called during every TLS handshake: the server computes d = e^{-1} mod phi(n).

**Modular inverse:** a^{-1} mod n - a number x in {1, ..., n-1} such that a*x ≡ 1 (mod n). **Exists if and only if gcd(a, n) = 1.** **Three ways to find it:** 1. Extended Euclid: ax + ny = 1 - then x = a^{-1} mod n 2. Euler's formula: a^{-1} ≡ a^{phi(n)-1} (mod n) 3. For prime p: a^{-1} ≡ a^{p-2} (mod p) (Fermat's little theorem)

Bitcoin transactions are signed with ECDSA over Z/pZ, where p is a 256-bit prime. The signature requires computing k^{-1} mod p - the inverse of a random nonce. Reusing the same nonce twice allows recovery of the private key. That is exactly how Sony PlayStation 3 was broken in 2010: a fixed nonce in ECDSA exposed every device's private key.

Chinese Remainder Theorem

3rd-5th century CE. The Chinese mathematician Sun Tzu writes: "An unknown number. Divided by three, remainder two. By five, remainder three. By seven, remainder two. What is the number?" The answer is twenty-three. But the real answer is not the number - it is the method: if the remainders modulo several pairwise coprime moduli are known, the number itself is uniquely determined.

**Chinese Remainder Theorem (CRT):** If n1, n2, ..., nk are pairwise coprime, then the system: x ≡ a1 (mod n1) x ≡ a2 (mod n2) ... x ≡ ak (mod nk) has a **unique** solution modulo N = n1 * n2 * ... * nk. **Construction:** N_i = N / n_i, then x = sum(a_i * N_i * N_i^{-1} mod n_i) mod N

RSA uses CRT to speed up decryption by a factor of four. Instead of computing c^d mod n (n is a 2048-bit number), the computation is split: c^d mod p and c^d mod q separately - numbers half the size, exponentiation four times faster. CRT then reconstructs the result mod n. This is the RSA-CRT optimization built into OpenSSL.

Shamir's secret sharing - distributing a secret without a central holder - also relies on CRT. The secret is split into k shares such that any t of them reconstruct it via polynomial interpolation in Z/pZ, while t-1 shares reveal nothing. Federated learning uses the same idea for gradient aggregation without exposing local data.

Key Ideas

• **Congruences:** a ≡ b (mod n) - same remainders; preserved under +, * but not division without conditions
• **Z/nZ:** ring of residues; Z/pZ is a field (GF(p)) when p is prime - the foundation of AES and Reed-Solomon
• **Modular inverse:** a^{-1} mod n exists if and only if gcd(a,n) = 1; found via extended Euclid in O(log n)
• **CRT:** a system with pairwise coprime moduli has a unique solution mod N = product of moduli

Related Topics

Modular arithmetic bridges number theory and cryptography:

• Euclidean Algorithm and GCD — Extended Euclid is the primary tool for computing modular inverses
• Divisibility and Prime Numbers — Prime moduli yield fields GF(p); the factorization of n determines the structure of Z/nZ
• Fermat's Little Theorem — Gives an alternative path to a^{-1} mod p via fast exponentiation

Вопросы для размышления

• Why does RSA use the modulus n = p*q rather than a large prime? What is lost with phi(p) and what is gained with phi(p*q)?
• The Euclidean algorithm (around 300 BCE) runs inside OpenSSL at every TLS handshake. How many times per second is it executed across the entire internet right now?
• How does Shamir's secret sharing use polynomial interpolation in Z/pZ so that t-1 shares reveal nothing, but t shares reconstruct the secret completely?

Связанные уроки

• nt-02 — Extended Euclid is the only tool for computing a^{-1} mod n
• nt-04 — Fermat's little theorem gives an alternative route to the modular inverse
• nt-01 — Prime moduli yield fields; composite ones yield rings with zero divisors
• alg-01-big-o — O(log n) of extended Euclid is the same class as binary search
• prob-04-bayes — CRT and Bayes both reconstruct the whole from partial information
• crypto-02-modular-arithmetic