Modular Arithmetic

Цели урока

• Understand modular operations and the square-and-multiply algorithm
• Apply Euclid's algorithm to find GCD and modular inverses
• Use the multiplicative inverse to understand RSA
• Apply CRT to optimize cryptographic computations

RSA-2048 rests on a single theorem Euler published in 1736. Thousands of HTTPS connections per second - modular arithmetic. A Bitcoin wallet - an elliptic curve over a finite field. All of modern cryptography is modular arithmetic with large numbers.

• **RSA encryption** - every HTTPS connection: a browser computes m^e mod n with 2048-bit numbers in milliseconds thanks to square-and-multiply
• **TLS handshake** - 10-50 ms includes several modular exponentiations with 2048-bit numbers
• **RSA-CRT in OpenSSL** - decryption 4x faster: a server handling 10K TLS connections/sec without CRT simply could not keep up
• **Key generation** - when creating an RSA key, extended Euclid finds d = e^(-1) mod phi(n): without the inverse, decryption is impossible
• **Bitcoin ECDSA** - signing a transaction: scalar multiplication of a curve point mod p_secp256k1 (256-bit prime)
• **AES in GF(2^8)** - SBox and MixColumns operate in a Galois field mod an irreducible polynomial - same modular arithmetic, different structure

Leonhard Euler and the theorem that underpins RSA

In 1736 Euler published «Theorema arithmeticum» - a generalization of Fermat's little theorem to composite numbers. Euler's theorem: for any a coprime with n, a^phi(n) = 1 (mod n), where phi(n) is Euler's totient function (count of integers coprime with n up to n). In 1977 Rivest, Shamir and Adleman showed that the theorem from 1736 becomes RSA encryption. Neither Euler nor his contemporaries could have imagined that 'pure mathematics' would protect trillions of dollars in transactions daily 240 years later.

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

• Introduction to Cryptography

Modular Operations

RSA-2048 rests on a single theorem Euler published in 1736. Thousands of HTTPS connections per second - modular arithmetic. A Bitcoin wallet - an elliptic curve over a finite field. All modern cryptography is numbers that wrap around in a cycle. **a mod n** is the remainder when a is divided by n. 15 mod 12 = 3: the number wrapped, like a clock hand. In cryptography the modulus is not 12 but a 2048-bit prime.

The key property: **the remainder can be taken at each step**. (a + b) mod n = ((a mod n) + (b mod n)) mod n. The same holds for multiplication. Intermediate results never grow to astronomical sizes. RSA works with 2048-bit numbers - without this property the arithmetic would be computationally impossible.

**Properties of modular arithmetic:** - Associativity, commutativity, distributivity - same as ordinary arithmetic - Closure: result always in [0, n-1] - Division - NOT like ordinary arithmetic: one cannot simply divide, a multiplicative inverse is required

**Modular exponentiation** is the operation on which RSA depends. Encryption: c = m^e mod n. The naive approach (compute m^e first, then mod n) is impossible: m^e with e = 65537 is a number with millions of digits. The **square-and-multiply** algorithm takes the remainder at every step, keeping numbers small. O(log e) multiplications instead of O(e).

`pow(base, exp, mod)` is the workhorse of cryptography. O(log exp) instead of O(exp). The difference: pow(2, 10^6, n) - 20 iterations, instant. 2^(10^6) - a number with 301030 digits, storage alone requires hundreds of kilobytes. Every RSA, Diffie-Hellman, and DSA operation reduces to one call to this function.

GCD and Euclid's Algorithm

300 BC. Euclid writes down an algorithm for finding the greatest common divisor. 2300 years later the same algorithm runs inside every cryptographic library during RSA key generation. Not because nothing better was found - but because GCD(a, b) = GCD(b, a mod b) is flawless. **GCD(a, n) = 1** means the numbers are coprime - and the modular inverse exists.

The brilliance of the algorithm is in the recursion: GCD does not reduce numbers linearly, it compresses them geometrically through mod. Two 2048-bit numbers - 2048 steps. A full divisor search would be 2^2048 steps - meaning never.

**Extended Euclidean Algorithm and Bezout's Identity:** For any a and b there exist x and y: **a * x + b * y = GCD(a, b)** If GCD(a, n) = 1, then a * x + n * y = 1, meaning a * x = 1 (mod n). In other words, x is the **multiplicative inverse** of a. The extended Euclid is the primary tool for finding inverses.

**Coprimality** is the central concept for cryptography. GCD(8, 15) = 1 - coprime, even though neither 8 nor 15 is prime. In RSA: the public exponent e must be coprime with phi(n). If not - no inverse exists, decryption is impossible.

Multiplicative Inverse

In ordinary arithmetic the inverse of 5 is 1/5. In modular arithmetic fractions do not exist. But the idea is the same: the **multiplicative inverse** a^(-1) mod n is the number that, when multiplied by a, gives 1. 3 * 5 = 15 mod 7 = 1: the inverse of 3 modulo 7 is 5. Without this concept RSA decryption does not exist.

Two methods for finding the inverse: the **extended Euclidean algorithm** (for any modulus) and **Fermat's little theorem** (only for prime p). Fermat: if p is prime, a^(p-1) = 1 (mod p), so a^(-1) = a^(p-2) mod p. Concise and compact.

**Fermat's Little Theorem:** If p is prime and p does not divide a: a^(p-1) = 1 (mod p) Consequence: a^(-1) = a^(p-2) (mod p) Example: inverse of 3 modulo 7 3^5 = 243, 243 mod 7 = 5 Check: 3 * 5 = 15 mod 7 = 1 Works ONLY when the modulus is prime.

In RSA the multiplicative inverse is at the heart of the algorithm. Public key: e. Private key d = e^(-1) mod phi(n). Encryption: c = m^e mod n. Decryption: m = c^d mod n. This works precisely because e*d = 1 (mod phi(n)). Without the inverse, decryption would be mathematically impossible.

Chinese Remainder Theorem (CRT)

3rd century AD. Chinese mathematician Sun Tzu poses a problem: a number gives remainder 2 when divided by 3, remainder 3 when divided by 5, remainder 2 when divided by 7. Find the number. The answer is 23. This result grew into the **Chinese Remainder Theorem**: when moduli are pairwise coprime, the system of congruences has a unique solution. In the 21st century - that is a 4x speedup for RSA.

CRT algorithm: M = product of all moduli. For each m_i compute M_i = M / m_i and inverse y_i = M_i^(-1) mod m_i. Solution: x = (sum r_i * M_i * y_i) mod M. Inverses always exist - the moduli are pairwise coprime by assumption.

**CRT in RSA: decryption 4x faster** RSA: m = c^d mod n, where n = p * q (2048 bits). Direct exponentiation is slow. RSA-CRT: 1. m_p = c^(d mod (p-1)) mod p (computation mod 1024-bit p) 2. m_q = c^(d mod (q-1)) mod q (computation mod 1024-bit q) 3. Combine via CRT Why 4x? Exponentiation cost scales as k^2: 2 * (k/2)^2 = k^2/2 instead of k^2. Plus exponents are half as long. Total ~4x. All real TLS implementations use RSA-CRT.

On a server handling thousands of TLS connections per second RSA-CRT is not an optimization - it is a survival requirement. OpenSSL, BoringSSL, LibreSSL all implement CRT by default. Garner's algorithm (incremental reconstruction through one precomputed inverse) is the industry standard.

Key ideas

• **Modular operations:** numbers wrap around after the modulus - like a clock hand. pow(base, exp, mod) - O(log exp), keeps intermediate numbers small. Without this RSA is computationally impossible
• **Euclid's algorithm 300 BC:** GCD(a, b) = GCD(b, a mod b) - O(log n) steps. The extended version yields Bezout coefficients and directly produces the multiplicative inverse
• **Multiplicative inverse:** a^(-1) mod n exists if and only if GCD(a, n) = 1. The RSA private key d = e^(-1) mod phi(n) is the inverse of public e
• **CRT:** a system with pairwise coprime moduli has a unique solution. RSA-CRT speeds decryption 4x - 3rd-century algebra inside every OpenSSL binary
• **Euler's theorem 1736** - the mathematical foundation of RSA. 'Pure mathematics' from 240 years ago protects internet transactions every day

Related topics

Modular arithmetic is the foundation of all cryptographic mathematics:

• Number Theory — Euler's theorem generalizes Fermat's little theorem to composite moduli - critical for RSA
• RSA: Mathematical Foundations — RSA directly uses all four lesson concepts: modular exponentiation, Euclid, inverse, CRT
• Algebraic Structures — Residues mod n form a ring, and a field when n is prime: inverse exists for all non-zero elements
• Elliptic Curves: Mathematics — ECC: point coordinates and operations over the curve - all computed modulo a large prime

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

• Why does division in modular arithmetic require finding an inverse instead of dividing directly? What exactly 'breaks' when dividing residues?
• Euclid's algorithm has existed for 2300 years unchanged. What properties make it optimal for cryptographic libraries?
• If CRT gives 4x speedup for RSA-2048, why not split into more factors for 8x? What security limitations does that create?

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

• crypto-03-number-theory — Euler's theorem and quadratic residues build on mod arithmetic
• crypto-24-rsa-math — RSA is a direct application of all four lesson concepts
• crypto-26-ecc-math — ECC operates in fields mod p - same arithmetic, different structure
• ar-28-modular — Modular arithmetic in the broader context of number theory
• alg-01-big-o — O(log n) complexity - foundation for understanding square-and-multiply speed
• bc-02-hashing — Hash functions and mod operations - both tools of one-wayness in cryptography
• dm-14