Modular arithmetic

Why 9 hours after 10 o'clock is 7, not 19

Modular arithmetic is maths where numbers wrap around at a fixed size n, called the modulus. 'a mod n' is the remainder of a ÷ n. A clock is mod 12: 10 + 9 = 19, which wraps around to 7.

Numbers with the same remainder are called congruent, written 19 ≡ 7 (mod 12). To add, subtract or multiply, work it out as usual and then take the remainder. Subtraction wraps backwards, so 1 − 3 ≡ 10 (mod 12).

To divide, you multiply by an inverse, the number that gives 1 when you multiply by it. Mod 7, 3 × 5 = 15 ≡ 1, so 5 acts as 1/3. With a prime modulus, every non-zero number has an inverse.

Modular arithmetic

Your bank catches a mistyped IBAN before the money leaves

Every IBAN carries two check digits set using mod 97. The bank moves the first four characters to the end, turns letters into numbers (A = 10) and checks that the result mod 97 equals 1. A typo fails this check.

The same arithmetic runs where you can't see it. RSA and Diffie–Hellman calculate mod numbers hundreds of digits long, and the X25519 key exchange used in TLS and Signal works mod the prime 2²⁵⁵ − 19.

Modular arithmetic

Take the remainder after every step and the numbers never get huge

Taking the remainder after every step gives the same final answer, so numbers stay below about n². Without this, a 600-digit number raised to a 600-digit power would have more digits than the universe has atoms.

Powers are worked out by squaring again and again and reducing each time, so a 2048-bit exponent takes a few thousand multiplications: milliseconds. The wraparound also hides the input, as many inputs share one remainder.