Secrets from Primes

Chapter 2 Modular arithmetic

Clock arithmetic

On a clock, 9 o'clock plus 5 hours is 2 o'clock. Arithmetic that wraps around like this has its own rules for division and powers, and they are the rules cryptography is built from.

10 min read · 5 interactive figures · 3 questions

A twelve-hour dial. The hand starts at a = 9; adding b = 5 walks five hours forward and lands on 2, because 9 + 5 = 14 leaves remainder 2 on division by 12. Drag the hand, or change a, b and the number of hours n.

Modular arithmetic is arithmetic that wraps around, like the hours on a clock. You work with whole numbers but keep only the remainder after dividing by a fixed number n, the modulus. On a 12-hour clock, 9 + 5 = 14 lands on 2, so 9 + 5 ≡ 2 (mod 12). Addition, subtraction and multiplication work as usual; division and powers are where it gets interesting, and where cryptography lives.

The dial at the top of this page is the picture to keep in mind. Every number is placed at the hour equal to its remainder: 14, 26 and −10 all sit at 2 on a 12-hour clock. This chapter builds, one step at a time, the four facts about the dial that chapter 3 needs: which numbers can be divided by, how to find the inverse that does it, what happens when you raise numbers to powers on a prime clock, and why even an exponent with hundreds of digits takes only a moment to compute.

Clock arithmetic and the notation for it

Drag the hand on the dial above, or push b past 12, and watch the walk wrap around. The hand only ever cares about the remainder. Two numbers that leave the same remainder on division by n land on the same hour, and mathematicians write this as

a ≡ b (mod n) means n divides a − b(1)

read “a is congruent to b modulo n”[1]. So 14 ≡ 2 (mod 12), since 12 divides 12, and −10 ≡ 2 (mod 12), since 12 divides −12. The operation “mod” on its own (as in 14 mod 12 = 2) means the remainder, always taken in 0 to n − 1; that is the hour the hand points to. For negative numbers this differs from what many programming languages give: −7 mod 5 is 3 here (−7 = −2 × 5 + 3), where JavaScript's % operator returns −2.

The useful fact is that congruence respects addition and multiplication: if a ≡ a′ and b ≡ b′, then a + b ≡ a′ + b′ and ab ≡ a′b′ (mod n)[1] established. You can reduce at every step. That is why the last digit of 7100 can be found in your head: work mod 10, where 7, 49 ≡ 9, 63 ≡ 3, 21 ≡ 1 repeat every four powers, so 7100 = (74)25 ≡ 1 and the last digit is 1.

Dividing on a clock: when an inverse exists

Ordinary division asks: what do I multiply 3 by to get 1? On the real line the answer is 1/3, but a clock has only whole hours. The question becomes: which hour x has 3x ≡ 1 (mod n)? Such an x is called the inverse of 3 modulo n, written 3−1. Modulo 10, 3 × 7 = 21 ≡ 1, so 3−1 ≡ 7. Dividing by 3 is the same as multiplying by 7.

Question 1 Prediction: which number has no inverse mod 10?#
Figure 1 Multiplication by k on a dial of n hours: a chord runs from every hour x to k·x mod n. Red dots are hours that something lands on; hollow dots are hours nothing reaches. It starts at k = 3, n = 10: every hour is hit once, and the green chord shows which hour is sent to 1 (the inverse). Move the slider to k = 4, or tap an hour on the rim to choose k.#

With k = 3 the chords form a permutation: every hour is hit exactly once, so the map can be run backwards, and the hour sent to 1 is the inverse. With k = 4 the chords pile up: the multiples of 4 land only on the even hours, two arrows on each, and hour 1 is never reached. The rule, which you can test on any dial, is[1] established

a has an inverse modulo n exactly when gcd(a, n) = 1(2)

where gcd is the greatest common divisor. If a and n share a factor d > 1, every multiple of a reduced mod n is still a multiple of d, so it can never be 1. On a prime clock nothing from 1 to p − 1 shares a factor with p, so every nonzero hour has an inverse. Prime moduli make division always possible, which is one reason cryptography prefers them. Try n = 11 and any k other than 0.

Finding the inverse by trying every hour is fine on a 10-hour clock and hopeless on a clock with 600-digit hours. The fast method is Euclid's algorithm for the gcd, extended to keep track of how each remainder is built[1]. Divide n by a, then a by the remainder, and so on; alongside each remainder r, record numbers s and t with r = a·s + n·t. When the remainder reaches gcd(a, n) = 1, its row reads a·s + n·t = 1, and reducing mod n gives a·s ≡ 1. So s is the inverse. The number of steps grows only with the number of digits, so 600-digit inverses take a few thousand steps.

Figure 2 The extended Euclidean algorithm finding the inverse of 17 modulo 3120, the pair that appears in the RSA example of chapter 3. Each row of the table is a remainder r with r = 17·s + 3120·t. Change a or n (try 4 and 10), or pick another operation; numbers may have up to 400 digits.#

Powers on a prime clock: Fermat's little theorem

Now raise a number to powers and follow it around the dial. On a 7-hour clock, the powers of 3 are 1, 3, 9 ≡ 2, 6, 18 ≡ 4, 12 ≡ 5, 15 ≡ 1: after six steps they are back at 1, and from then on they repeat.

Question 2 Prediction: powers on a prime clock#
Figure 3 The powers g0 = 1, g1, g2, … modulo n, joined in order by red chords; the hand shows gt. It starts with powers of 3 on a 7-hour clock, which visit all six nonzero hours before returning to 1 (green). Try g = 2 (three steps), then other primes n such as 11 or 13, and then a composite such as 12. Tap an hour on the rim to choose g.#

On every prime clock and for every nonzero base, the powers return to 1, and the number of steps they take (the order of g) always divides p − 1. Powers of 2 on the 7-hour clock take three steps; powers of 6 take two; powers of 3 take all six. Since every order divides p − 1, walking p − 1 steps always lands on 1:

ap−1 ≡ 1 (mod p) for prime p and p ∤ a(3)

This is Fermat's little theorem, named after Pierre de Fermat[1] established. The reason the orders divide p − 1 is a counting argument: the hours visited by the powers of g form a closed loop, and the p − 1 nonzero hours split into copies of that loop of equal size (multiply the loop by any hour not on it to get another). A base like 3 modulo 7, whose powers visit every nonzero hour, is called a generator or primitive root; every prime has at least one[1].

For a composite modulus the same reasoning works on the hours that share no factor with n. There are φ(n) of them (Euler's totient), and Euler's theorem says aφ(n) ≡ 1 (mod n) whenever gcd(a, n) = 1[1] established. For n = p × q, a product of two different primes, φ(n) = (p − 1)(q − 1). Remember that formula: computing it requires knowing p and q, and it is the hinge of RSA. On the dial, set n = 12 and g = 2: the powers 1, 2, 4, 8, 4, 8, … never return to 1, because 2 shares a factor with 12.

Fermat's theorem is also the basis of the primality test in chapter 1: if an−1 mod n is not 1, then n cannot be prime. Composite numbers that pass anyway, such as 561, exist because their orders happen to divide n − 1 too. For 561 = 3 × 11 × 17 every order divides 80, and 80 divides 560[2].

Huge powers in a few steps

RSA raises numbers with hundreds of digits to exponents with hundreds of digits. Multiplying the base by itself one step at a time would take longer than the age of the universe. Yet the computation is fast. How fast?

Question 3 Prediction: how many multiplications for 7^1000?#
Figure 4 71000 mod 13 by square-and-multiply. The top row is the exponent 1000 in binary, 1111101000. The first digit starts the value at 7; each later digit squares it (second row), and each later 1 then multiplies it by 7 (third row): 9 squarings and 5 multiplications in all. The bottom row is the value after each digit, ending at 9. The bars compare the work with multiplying one factor at a time, on a logarithmic scale. Drag the exponent, or change the base and modulus.#

The trick is repeated squaring[1]. Squaring doubles the exponent, so after k squarings you have reached the power 2k. Any exponent is a sum of powers of 2 (its binary digits), so you multiply in the right squares as you go. An exponent with b binary digits needs b − 1 squarings and at most b − 1 further multiplications. A 2048-bit exponent needs at most about 4,000 multiplications instead of 22048. Because you reduce mod n after every step, no intermediate number is ever larger than n2. This is exactly how the modular arithmetic calculator computes powers of numbers with up to 400 digits, and how the strong primality test in chapter 1 runs so quickly.

A one-way door

Square-and-multiply makes it easy to go from g and x to gx mod p. Going back, from gx mod p to x, is called the discrete logarithm problem, and it is believed to be hard for well-chosen primes[1][3] active. On the 7-hour dial you can read the answer off the picture. On a dial with a 600-digit prime number of hours, the powers of a generator jump around with no visible pattern, and no known method finds x in a reasonable time for well-chosen primes. Ordinary logarithms are easy because powers of a real number grow smoothly; on a clock the wrapping destroys that order.

Notice that “believed” is doing real work in that paragraph. Nobody has proved that discrete logarithms, or factoring, are hard; they have resisted about fifty years of attack by very clever people, and standards bodies size their keys on that record[4] active. Large quantum computers, if they are built, would change the picture: NIST's key-size table carries a footnote warning that its estimates will be significantly affected once quantum computing becomes practical[4]. Chapter 3 uses the two one-way doors of this site, multiplying primes and raising to powers on a clock, to build the locks that protect web traffic.