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