Modular Arithmetic as Algebra: The Ring Behind RSA

Terminology

What & Why

Modular arithmetic is familiar to every programmer: the % operator. But viewed through the lens of abstract algebra, $\mathbb{Z}/n\mathbb{Z}$ is a ring with rich structure. The units (invertible elements) form a group $(\mathbb{Z}/n\mathbb{Z})^*$ whose size is Euler's totient $\phi(n)$. The Chinese Remainder Theorem decomposes this ring into simpler pieces. Together, these results form the algebraic foundation of RSA.

Why does this matter for CS?

• RSA cryptography: encryption computes $m^e \bmod n$, decryption computes $c^d \bmod n$, and correctness relies on Euler's theorem: $m^{ed} \equiv m \pmod{n}$ when $ed \equiv 1 \pmod{\phi(n)}$
• Hash function design: many hash functions use modular arithmetic to map keys to table indices. Understanding the ring structure explains why prime table sizes reduce collisions.
• Load balancing: consistent hashing maps servers and keys to positions on a modular ring $\mathbb{Z}/m\mathbb{Z}$
• CRT-based speedups: RSA implementations use the Chinese Remainder Theorem to speed up decryption by a factor of ~4x, computing mod $p$ and mod $q$ separately

How It Works

The Ring $\mathbb{Z}/n\mathbb{Z}$ and Its Units

The ring $\mathbb{Z}/n\mathbb{Z}$ has $n$ elements. An element $a$ is a unit (has a multiplicative inverse) if and only if $\gcd(a, n) = 1$. The set of all units forms the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^*$.

Euler's Totient Function

For $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$:

Special cases:

• $\phi(p) = p - 1$ for prime $p$
• $\phi(p^k) = p^{k-1}(p - 1)$
• $\phi(pq) = (p-1)(q-1)$ for distinct primes $p, q$ (this is the RSA case)

The Chinese Remainder Theorem

If $\gcd(m, n) = 1$, then the ring isomorphism holds:

This means solving a system of congruences $x \equiv a \pmod{m}$, $x \equiv b \pmod{n}$ has a unique solution mod $mn$. For RSA with $n = pq$, CRT lets us compute $m^d \bmod n$ by separately computing $m^d \bmod p$ and $m^d \bmod q$, then combining. Since the moduli are half the size, each exponentiation is ~4x faster.

RSA: The Algebraic View

Choose primes $p, q$, set $n = pq$. Pick $e$ coprime to $\phi(n) = (p-1)(q-1)$, compute $d \equiv e^{-1} \pmod{\phi(n)}$. Then:

The last step uses Euler's theorem. This is why RSA decryption recovers the original message.

Complexity Analysis

The CRT speedup is why every real RSA implementation stores $p$, $q$, $d \bmod (p-1)$, and $d \bmod (q-1)$ alongside the private key.

Implementation

ALGORITHM EulerTotient(n, prime_factors)
INPUT:  n: positive integer
        prime_factors: list of distinct prime factors of n
OUTPUT: phi(n)

BEGIN
  result := n

  FOR EACH p IN prime_factors DO
    result := result - result / p    // integer division: result * (1 - 1/p)
  END FOR

  RETURN result
END

ALGORITHM CRT_Solve(a, m, b, n_mod)
INPUT:  a, m, b, n_mod: integers with gcd(m, n_mod) = 1
        Find x such that x = a (mod m) and x = b (mod n_mod)
OUTPUT: x in [0, m * n_mod)

BEGIN
  (g, u, v) := ExtendedGCD(m, n_mod)
  // u*m + v*n_mod = 1

  x := a * v * n_mod + b * u * m
  x := x MOD (m * n_mod)

  IF x < 0 THEN
    x := x + m * n_mod
  END IF

  RETURN x
END

ALGORITHM RSA_Decrypt_CRT(c, p, q, dp, dq, q_inv)
INPUT:  c: ciphertext
        p, q: prime factors of n
        dp: d mod (p-1)
        dq: d mod (q-1)
        q_inv: q^{-1} mod p
OUTPUT: plaintext m = c^d mod (p*q)

BEGIN
  // Compute partial results mod p and mod q
  m1 := RepeatedSquaring(c MOD p, dp, p)
  m2 := RepeatedSquaring(c MOD q, dq, q)

  // Combine using Garner's formula (variant of CRT)
  h := (q_inv * (m1 - m2)) MOD p
  IF h < 0 THEN
    h := h + p
  END IF

  m := m2 + h * q

  RETURN m
END

Real-World Applications

• RSA encryption/decryption: the entire RSA system is built on modular arithmetic in $\mathbb{Z}/n\mathbb{Z}$. Key generation uses $\phi(n)$, encryption/decryption use modular exponentiation, and CRT accelerates private key operations.
• Hash tables: hash functions often compute $h(k) = k \bmod m$. Choosing $m$ to be prime avoids patterns in the input from causing clustering, because $\mathbb{Z}/p\mathbb{Z}$ has no zero divisors.
• Consistent hashing: distributed systems map keys and servers to positions on a ring $\mathbb{Z}/m\mathbb{Z}$, using the modular structure for uniform distribution and minimal remapping on server changes.
• Checksums and error detection: ISBN check digits, credit card Luhn checks, and UPC barcodes all use modular arithmetic for error detection.
• Pseudorandom number generators: linear congruential generators compute $x_{n+1} = (ax_n + c) \bmod m$, and the period depends on the algebraic properties of $a$ and $m$ in $\mathbb{Z}/m\mathbb{Z}$.
• Scheduling and circular buffers: ring buffers use modular indexing ($i \bmod n$) to wrap around, directly implementing $\mathbb{Z}/n\mathbb{Z}$ addition.

Key Takeaways

• $\mathbb{Z}/n\mathbb{Z}$ is a ring; its units (elements coprime to $n$) form the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^*$ of size $\phi(n)$
• Euler's theorem ($a^{\phi(n)} \equiv 1$) is the algebraic reason RSA decryption recovers the original message
• The Chinese Remainder Theorem decomposes $\mathbb{Z}/mn\mathbb{Z}$ into $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$, enabling a ~4x speedup for RSA decryption
• Choosing prime moduli for hash tables avoids zero divisors and reduces collision patterns
• Modular arithmetic appears in hash functions, consistent hashing, checksums, PRNGs, and circular buffers