Modular Arithmetic

5 min read#cryptography

Arithmetic that wraps around a fixed modulus — the finite-ring algebra that makes public-key cryptography possible.

Contents

Modular Arithmetic

Modular arithmetic is arithmetic that wraps around. On a 12-hour clock, 4 hours after 10 o'clock is not 14 — it is 2, because we wrap at 12. Written formally, 10 + 4 \equiv 2 \pmod{12}. We say two numbers are congruent mod n when they leave the same remainder on division by n:

a \equiv b \pmod{n} \quad\Longleftrightarrow\quad n \text{ divides } (a - b).

Fix a modulus n and the integers collapse into just n residues, \{0, 1, \dots, n-1\} — a finite ring. Addition, subtraction, and multiplication all still work; results simply fold back into that range. This little finite world is the stage on which RSA and Diffie–Hellman perform.

Powers that cycle

The operation that powers public-key cryptography is modular exponentiation: computing a^k \bmod n. Because there are only finitely many residues, the powers a^1, a^2, a^3, \dots can never run off to infinity — they must eventually repeat, tracing a cycle through the ring. Watch one form.

Points 0…n−1 sit around a ring (n = 17). Drag left↔right to choose the base a; the orange hop walks a, a², a³, … mod n. The trail closes into a loop — the order of a. Some bases visit every nonzero point; others get stuck in a short cycle.

When n is prime, some bases are generators: their powers visit every nonzero residue before returning home. That property is exactly what Diffie–Hellman needs.

The two trapdoors crypto leans on

Modular arithmetic matters to cryptography because it hides operations that are easy one way, brutally hard to reverse inside its finite ring.

  • Modular exponentiation is fast. Even for thousand-digit numbers, a^k \bmod n takes only a few dozen squarings (repeatedly square and multiply). Going forward is cheap.
  • The inverse is hard. Recovering k from a^k \bmod n — the discrete logarithm — has no known fast method for well-chosen n. That asymmetry is the trapdoor under Diffie–Hellman.
  • Factoring is hard. Multiplying two large primes p \cdot q = n is instant; splitting n back into p and q is believed intractable. That is the trapdoor under RSA.

On a 12-hour clock, what is 7 × 5 mod 12?

See also