Modular Arithmetic and Primes for Cryptography

Two integers $a$ and $b$ are congruent modulo $n$, written $a \equiv b \pmod n$, if $n$ divides $a - b$. Equivalently, $a$ and $b$ leave the same remainder when divided by $n$. This relation partitions the integers into $n$ residue classes, usually represented by $\{0, 1, \dots, n-1\}$, and the set of these classes with addition and multiplication defined "mod $n$" is denoted $\mathbb{Z}_n$. Congruence behaves like equality for the purposes of addition, subtraction, and multiplication: if $a \equiv b \pmod n$ and $c \equiv d \pmod n$, then $a+c \equiv b+d$, and $ac \equiv bd \pmod n$. This is why we can reduce intermediate results modulo $n$ at any point in a computation without changing the final answer — the key property that makes modular arithmetic tractable on computers, where numbers never grow unboundedly large. Division is subtler. In ordinary arithmetic, dividing by $a$ means multiplying by $1/a$. In $\mathbb{Z}_n$, we instead seek a modular inverse: an integer $a^{-1}$ such that $a \cdot a^{-1} \equiv 1 \pmod n$. Such an inverse exists if and only if $\gcd(a, n) = 1$, i.e., $a$ and $n$ are coprime. This is not a technicality — it is the crux of why cryptographic moduli are built from primes or products of primes: they guarantee that almost every element has an inverse, or that we can precisely control which elements do. Two theorems anchor everything that follows. Fermat's Little Theorem says that if $p$ is prime and $\gcd(a,p)=1$, then $a^{p-1} \equiv 1 \pmod p$. Euler's Theorem generalizes this to any modulus $n$: if $\gcd(a,n)=1$, then $a^{\phi(n)} \equiv 1 \pmod n$, where $\phi(n)$ is Euler's totient function, counting integers in $\{1,\dots,n\}$ coprime to $n$. These theorems tell us the order of the multiplicative structure of $\mathbb{Z}_n$ and let us collapse enormous exponents down to something manageable — precisely the trick RSA uses to guarantee that encrypting then decrypting returns the original message. Together with the extended Euclidean algorithm for computing inverses, and primality tests for manufacturing large primes, these ideas form the complete algebraic substrate of The RSA Cryptosystem and set the stage for the multiplicative-group viewpoint needed in The Discrete Logarithm Problem.

The Euclidean algorithm (GCD)

The Euclidean algorithm computes $\gcd(a,b)$ using the identity $\gcd(a,b) = \gcd(b, a \bmod b)$, repeatedly reducing the problem until the second argument hits zero. ``` function GCD(a, b): while b != 0: (a, b) = (b, a mod b) return a ```

The extended Euclidean algorithm (modular inverse)

The extended version tracks coefficients so that at every step we maintain integers $x, y$ with $a x + b y = \gcd(a,b)$ (Bézout's identity). When $\gcd(a,n) = 1$, the coefficient of $a$ gives exactly the modular inverse of $a \pmod n$. ``` function ExtendedGCD(a, b): // returns (g, x, y) such that ax + by = g = gcd(a, b) (old_r, r) = (a, b) (old_s, s) = (1, 0) (old_t, t) = (0, 1) while r != 0: q = old_r div r (old_r, r) = (r, old_r - q r) (old_s, s) = (s, old_s - q s) (old_t, t) = (t, old_t - q * t) return (old_r, old_s, old_t) // g, x, y function ModInverse(a, n): (g, x, _) = ExtendedGCD(a, n) if g != 1: error "no inverse exists" return x mod n ```

Fast modular exponentiation

Cryptographic exponents are hundreds of digits long, so computing $a^b$ directly is impossible — the result would have more digits than atoms in the observable universe. Repeated squaring exploits the binary representation of the exponent, reducing $b$ multiplications to $O(\log b)$. ``` function ModExp(a, b, n): result = 1 a = a mod n while b > 0: if b is odd: result = (result a) mod n a = (a a) mod n b = b div 2 return result ```

Primality testing

To build a cryptosystem you must manufacture large primes, not just reason about them abstractly. The workhorse is a probabilistic test built on Fermat's theorem. ``` function FermatTest(p, k): // probabilistic: k independent witnesses if p < 2: return false for i = 1 to k: a = random integer in [2, p-2] if ModExp(a, p-1, p) != 1: return "composite" return "probably prime" ``` The Fermat test has rare false positives (Carmichael numbers), so real systems use the stronger Miller–Rabin test, which additionally checks nontrivial square roots of unity along the way, driving the error probability down to at most $4^{-k}$ for $k$ rounds.

Euclidean algorithm — complexity. Each step replaces $(a,b)$ with $(b, a \bmod b)$, and a classical fact (related to Fibonacci numbers) shows that $a \bmod b < a/2$ within two steps in the worst case. More precisely, the number of division steps is $O(\log(\min(a,b)))$; the worst case is achieved by consecutive Fibonacci numbers, giving the Euclidean algorithm its famous logarithmic bound (this is Lamé's theorem). Each step performs one integer division, so for $k$-bit numbers, the total bit complexity is $O(k^2)$ using schoolbook division, or better with fast multiplication. Correctness invariant: at every iteration, $\gcd(a,b)$ is unchanged, because any common divisor of $a$ and $b$ also divides $a \bmod b = a - qb$, and conversely. The loop terminates because $b$ strictly decreases and is a non-negative integer, so it must eventually hit $0$, at which point $a$ is the answer.

Extended Euclidean algorithm. Same $O(\log(\min(a,b)))$ iteration count; it additionally maintains the invariant $a \cdot s_i + n \cdot t_i = r_i$ at every step, which is preserved by construction of the update rule (it mirrors the same linear combination the quotient step performs on the remainders). When $r_i$ reaches $\gcd(a,n)$, the corresponding $s_i$ satisfies $a \cdot s_i \equiv \gcd(a,n) \pmod n$; if $\gcd(a,n)=1$ this is the inverse.

Existence of inverses. By Bézout's identity, $\gcd(a,n)=1$ implies integers $x,y$ exist with $ax + ny = 1$, so $ax \equiv 1 \pmod n$. Conversely, if $d = \gcd(a,n) > 1$, then $d \mid ax$ and $d \mid n$ for any $x$, so $ax \bmod n$ can never equal $1$. This "iff" is exact, not a heuristic — it is why RSA key generation insists the public exponent $e$ be coprime to $\phi(n)$.

Modular exponentiation. Repeated squaring uses $O(\log b)$ multiplications, each of numbers with at most $\log n$ bits, giving overall $O((\log b)(\log n)^2)$ bit operations with schoolbook multiplication. Naive repeated multiplication would take $O(b)$ multiplications — exponential in the bit-length of $b$ — so this is the difference between a computation finishing instantly and one that never finishes. Correctness: writing $b$ in binary as $b = \sum b_i 2^i$, we have $a^b = \prod_i a^{2^i \cdot b_i}$. The loop maintains the invariant that `a` holds $a_0^{2^i} \bmod n$ at the start of iteration $i$ (where $a_0$ is the original base) and `result` holds the product of all such terms for bits already processed — squaring `a` each round advances the exponent's power of two, and multiplying into `result` exactly when the bit is $1$ implements the product formula.

Fermat's Little Theorem — proof sketch. For prime $p$ and $a$ not divisible by $p$, the map $x \mapsto ax \bmod p$ permutes the nonzero residues $\{1, \dots, p-1\}$ (it is injective because $p$ is prime and has no inverse issues, hence bijective on a finite set). Multiplying all of them together, $\prod_{x=1}^{p-1} (ax \bmod p) = \prod_{x=1}^{p-1} x$, and factoring $a$ out of each of the $p-1$ terms gives $a^{p-1} \prod x \equiv \prod x \pmod p$. Since $\prod x$ is coprime to $p$, it cancels, leaving $a^{p-1} \equiv 1 \pmod p$.

Euler's Theorem is the same argument run over the group of units modulo $n$ (residues coprime to $n$, of which there are $\phi(n)$) instead of all nonzero residues modulo a prime; it reduces to Fermat's theorem exactly when $n = p$ is prime, since then $\phi(p) = p - 1$.

Primality testing — honest tradeoffs. Trial division is $O(\sqrt{p})$ and exact but useless for 1024-bit primes ($\sqrt p$ is astronomically large). The Fermat test is fast ($O(\log p)$ modular exponentiations) but can be fooled by Carmichael numbers, which satisfy Fermat's congruence for every base despite being composite. Miller–Rabin fixes this by also checking for nontrivial square roots of $1$ modulo $p$ (a prime modulus has only $\pm 1$ as square roots of $1$); it errs with probability at most $4^{-k}$ over $k$ random rounds, and no known efficient deterministic test beats this in practice for cryptographic sizes — hence real systems accept a tunably tiny, non-zero error probability.

Let's actually build a tiny (insecure, illustrative) RSA-style key pair and trace every tool above on real numbers.

Step 1 — pick primes. Let $p = 61$, $q = 53$. (Trial division instantly confirms both are prime; in practice Miller–Rabin would certify 300-digit primes this size in milliseconds.)

Step 2 — modulus and totient.

Step 3 — choose public exponent $e$, coprime to $\phi(n)$. Try $e = 17$. Run the Euclidean algorithm on $\gcd(17, 3120)$:

$b$ reaches $0$ with $a = 1$, so $\gcd(17, 3120) = 1$ — a valid exponent.

Step 4 — compute the private exponent $d = e^{-1} \bmod \phi(n)$ via extended Euclid. Tracking Bézout coefficients through the same division chain (3120 = 183·17 + 9, 17 = 1·9 + 8, 9 = 1·8 + 1, 8 = 8·1 + 0) and back-substituting:

So $-367 \cdot 17 \equiv 1 \pmod{3120}$, giving $d \equiv -367 \equiv 2753 \pmod{3120}$. Check: $17 \times 2753 = 46801 = 15 \times 3120 + 1$. ✓ Confirmed: $d = 2753$.

Step 5 — encrypt a message $m = 65$ (e.g. the ASCII code for 'A') using $c = m^e \bmod n$, via repeated squaring with $e=17=10001_2$:

So $c = 65^{17} \bmod 3233 = 2790$.

Step 6 — decrypt using $m = c^d \bmod n = 2790^{2753} \bmod 3233$. Repeated squaring (2753 has 12 bits) runs in $O(\log d) \approx 12$ squarings and a handful of multiplications, and returns $m = 65$ — recovering the original message exactly, as guaranteed by Euler's Theorem since $ed \equiv 1 \pmod{\phi(n)}$ forces $m^{ed} \equiv m \pmod n$. This tiny trace is RSA in miniature: everything from here to The RSA Cryptosystem is scaling $p,q$ up to hundreds of digits and hardening the primality test.

Every TLS handshake that secures an HTTPS connection performs modular exponentiation, whether through RSA key transport or Diffie–Hellman key exchange, both living entirely inside the arithmetic developed here. Digital signature schemes — RSA-PSS, DSA, and elliptic-curve variants — use modular inverses to compute signatures and verify them, and the generation of the underlying keys depends on manufacturing large primes with tests like Miller–Rabin. Cryptographic libraries such as OpenSSL, libsodium, and hardware security modules implement fast modular exponentiation as a performance-critical primitive, often in constant time to defend against timing side-channels that could otherwise leak secret exponents bit by bit. Beyond classical public-key systems, the same modular structures reappear in the group-theoretic setting of The Discrete Logarithm Problem, which underlies Diffie–Hellman and elliptic-curve cryptography, and understanding Modular Exponentiation here is a direct prerequisite to reasoning about The RSA Cryptosystem's correctness and security proofs.

Ask the tutor: Can you walk through why choosing $e$ coprime to $\phi(n)$ is both necessary and sufficient for RSA to always correctly decrypt every possible message?