Modular arithmetic and ciphers

The last chapter ended with a riddle: how can two people agree on a secret key if strangers overhear their whole conversation? Your phone solves it every day. Open your bank’s website. Between your phone and the bank’s server there’s café Wi-Fi, an internet provider, a dozen routers in different countries, and any of them could record every bit you send. You’ve never met your bank, and you never agreed on a password for encryption in advance. And yet in a fraction of a second the phone and the server agree on a secret key, and someone who has overheard their conversation from the first bit to the last can’t compute it.

To a cipher-maker of any century before the twentieth this would have looked like a conjuring trick. A cipher always began with a secret meeting: the key was passed from hand to hand, carried by a courier, sewn into a lining. Agreeing on a secret out loud, in front of witnesses, was impossible by definition. So people thought until 1976.

This chapter is a cipher-maker’s workshop. We’ll build several ciphers, from Caesar’s wheel to RSA, and try to break each. Between the ciphers we’ll sharpen our tools: congruences, inverses, the theorems of Fermat and Euler, the Chinese remainder theorem. At the end we’ll answer the course’s fifth big question: how does the cipher that protects your bank work?

Caesar’s wheel

Suetonius tells us that in his secret letters Julius Caesar replaced each letter by the third one after it: instead of A he wrote D, instead of B, E. Let’s build this cipher for the English alphabet. Number the letters from zero: $A = 0$, $B = 1$, …, $Z = 25$. To encrypt, add three to the letter’s number. The word CAESAR turns into FDHVDU.

A hitch comes at the end of the alphabet. The letter Z has number $25$, and $25 + 3 = 28$, but there’s no such letter. It’s natural to start the alphabet again, like the hand of a clock after twelve: $28$ turns into $28 - 26 = 2$, that is, C. The alphabet has curled up into a wheel of $26$ divisions. On this wheel $25 + 3 = 2$. That’s no mistake: it’s a different arithmetic, in which numbers differing by $26$ count as the same.

The first number: any integer, negative ones included. The second number. Usually $b$ is the remainder, the only number from $0$ to $n - 1$ congruent to $a$. The modulus, the “number of divisions” of the clock face. The sign $\mid$ reads “divides”. Example: $28 \equiv 2 \pmod{26}$, because $28 - 2 = 26$. A step back from the letter A leads to Z: $-1 \equiv 25 \pmod{26}$. Modulo $12$, $15$ and $3$ are congruent: fifteen o’clock is three in the afternoon.

Two numbers are congruent modulo $n$ exactly when they leave the same remainder on division by $n$. We proved this in chapter 4, in the lemma on remainders. The sign $\equiv$ and the word “congruence” itself were introduced by Gauss in his Disquisitiones Arithmeticae (1801). Before him the same thing was written in words, and with the new symbol it turned out that congruences can be handled almost like equations.

We’ve already met addition in $\mathbb Z_n$: in the chapter on groups it was the clock face, a cyclic group. The Caesar cipher is adding a key $k$ in this group, $y = x + k$, and decryption is adding $-k$. Now let’s add multiplication, and for that we need one theorem: congruences can be added and multiplied term by term, like equations.

The idea: the difference of the products $ab - a'b'$ is an L-shaped strip between two rectangles, and it can be cut into two pieces, each of which has one side a multiple of $n$.

Since $a \equiv a'$ and $b \equiv b'$, the differences $a - a'$ and $b - b'$ are divisible by $n$. In the picture $n = 3$: both differences are cut into segments of length $3$. The product $ab$ is the area of the big rectangle, $a'b'$ the area of the small one in its corner. The difference $ab - a'b'$ is an L-shaped strip. Cut it into two rectangles: the top one, $a \times (b - b')$, and the right one, $(a - a') \times b'$. Hence the identity $ab - a'b' = a(b - b') + (a - a')b'$. Multiply out the brackets, and it checks out for any integers, not just positive ones as in the picture. The top piece has the side $b - b'$ a multiple of $n$, the right piece the side $a - a'$. Each piece can be cut into strips of width $n$, so the area of each is divisible by $n$. So $n$ also divides the sum of the pieces, $ab - a'b'$, that is, $ab \equiv a'b' \pmod n$. With addition it’s even simpler: $(a + b) - (a' + b') = (a - a') + (b - b')$, a sum of two multiples of $n$.

The practical conclusion: in any expression made of additions, subtractions and multiplications, numbers can be replaced by congruent ones at any moment, and the answer modulo $n$ won’t change. Numbers can be reduced along the way, without waiting for them to grow. The last digit of the number $7^{2026}$ is its remainder modulo $10$. Notice that $7^2 = 49 \equiv -1 \pmod{10}$, so $7^4 \equiv (-1)^2 = 1$ and $7^{2026} = (7^4)^{506} \cdot 7^2 \equiv 1 \cdot 49 \equiv 9$. A number with more than seventeen hundred digits ends in a nine, and we didn’t have to compute it.

The divisibility tests from chapter 4 fit into one line in this language. Since $10 \equiv 1 \pmod 9$, every power of ten is congruent to one, and a number is congruent to the sum of its digits. Since $10 \equiv -1 \pmod{11}$, the powers of ten are congruent to $1$ and $-1$ in turn, hence the alternating sum. The “place weights” of that chapter are the remainders of the powers of ten.

The Caesar cipher breaks in a minute: there are only $26$ keys, and you can try them all until meaningful text shows through. Cipher-makers realised long ago that many keys are needed. You can, for example, encrypt by multiplying and shifting: $y \equiv ax + b \pmod{26}$. This is the affine cipher, and its key is the pair $(a, b)$. But multiplication on a clock face behaves in an unfamiliar way. Look at what it looks like.

The curves on the circle are beautiful in their own right. At $m = 2$ the chords join the angle $\theta$ to the angle $2\theta$, and their envelope is a cardioid. At $m = 3$ we get a nephroid: the same curve that sunlight reflected by the walls of a cup draws on the surface of your coffee. For a cipher the small clock face matters more. At $n = 10$ and $m = 3$ the arrows permute the points: each gets exactly one arrow. At $m = 4$ half the points get none, while others get two. A cipher with such a multiplier can’t be decrypted: two different letters turn into one.

The way back

To decrypt the affine cipher $y \equiv ax + b$ we have to express $x$: subtract $b$ and “divide by $a$”. Dividing on a clock face means multiplying by a number $a'$ such that $a \cdot a' \equiv 1$. For $a = 5$ modulo $26$ there is one: $5 \cdot 21 = 105 = 4 \cdot 26 + 1$. So from $y \equiv 5x + 8$ it follows that $x \equiv 21(y - 8) \pmod{26}$. The letter B ($x = 1$) is encrypted as $5 + 8 = 13$, that is, N, and back: $21 \cdot (13 - 8) = 105 \equiv 1$, B again.

The proof also suggests how to compute. The inverse is found by the extended Euclidean algorithm. Let’s find the inverse of $17$ modulo $43$. On the left is the forward pass of the algorithm, on the right the backward pass, as in the jugs problem:

$$\begin{aligned} 43 &= 2 \cdot 17 + 9, &\qquad 1 &= 9 - 8 \\ 17 &= 1 \cdot 9 + 8, & &= 9 - (17 - 9) = 2 \cdot 9 - 17 \\ 9 &= 1 \cdot 8 + 1, & &= 2 \cdot (43 - 2 \cdot 17) - 17 = 2 \cdot 43 - 5 \cdot 17. \end{aligned}$$

We’ve got $17 \cdot (-5) \equiv 1 \pmod{43}$, and the inverse of $17$ is $-5 \equiv 38$. Check: $17 \cdot 38 = 646 = 15 \cdot 43 + 1$. By Lamé’s theorem the algorithm makes at most five times as many divisions as there are digits, so a computer finds an inverse modulo a six-hundred-digit number instantly.

A prime modulus is especially good. If $p$ is prime, every number from $1$ to $p - 1$ is coprime to $p$ and so invertible. In $\mathbb Z_p$ you can divide by anything but zero, as with ordinary fractions. The non-zero remainders modulo a prime form a group under multiplication, and from now on it will be our main tool. Go back to the circle above: for a prime $n$ any multiplier $m$ from $1$ to $n - 1$ permutes the points.

How many solutions among the remainders $0, 1, \dots, 9$ does the congruence $6x \equiv 4 \pmod{10}$ have?

None: $6$ isn’t invertible modulo $10$ Exactly one Two Ten

$6 \cdot 4 = 24 \equiv 4$ and $6 \cdot 9 = 54 \equiv 4$. The congruence means that $10$ divides $6x - 4$, that is, $5$ divides $3x - 2$: $3x \equiv 2 \pmod 5$. Here three is invertible ($3 \cdot 2 = 6 \equiv 1$), and $x \equiv 2 \cdot 2 = 4 \pmod 5$. Modulo $10$ that’s two remainders: $4$ and $9$. If the right side were odd, there’d be no solutions at all: $6x - c$ would then be odd and not divisible by $10$.

An affine cipher for the $26$-letter Latin alphabet multiplies a letter’s number by $7$. What should you multiply by to decrypt? Find the inverse of $7$ modulo $26$ (a number from $0$ to $25$).

$26 = 3 \cdot 7 + 5$, $7 = 1 \cdot 5 + 2$, $5 = 2 \cdot 2 + 1$. The backward pass: $1 = 5 - 2 \cdot 2 = 5 - 2(7 - 5) = 3 \cdot 5 - 2 \cdot 7 = 3(26 - 3 \cdot 7) - 2 \cdot 7 = 3 \cdot 26 - 11 \cdot 7$. So $7^{-1} \equiv -11 \equiv 15 \pmod{26}$. Check: $7 \cdot 15 = 105 = 4 \cdot 26 + 1$.

Powers go round in circles

Addition modulo $n$ gave the Caesar cipher, multiplication the affine cipher. The next operation is raising to a power, and real cryptography begins with it. First let’s see how powers behave. The remainders of the powers of three on division by $7$: $3^1 = 3$, $3^2 = 9 \equiv 2$, $3^3 \equiv 2 \cdot 3 = 6$, $3^4 \equiv 6 \cdot 3 = 18 \equiv 4$, $3^5 \equiv 4 \cdot 3 = 12 \equiv 5$, $3^6 \equiv 5 \cdot 3 = 15 \equiv 1$. At the sixth step we’ve come back to one, and after that everything repeats: $3^7 \equiv 3$, $3^8 \equiv 2$, … The powers go round in a circle.

So $3^{100}$ modulo $7$ can be done in your head. Only the exponent up to multiples of six matters: $100 = 6 \cdot 16 + 4$, and $3^{100} = (3^6)^{16} \cdot 3^4 \equiv 1 \cdot 4 = 4 \pmod 7$. Is it a coincidence that the circle closed at the sixth step when the modulus is seven?

For every prime $n$ the last column, $k = n - 1$, consists entirely of ones. Different rows come back to one at different times: $2^3 \equiv 1 \pmod 7$, while three needs six steps. But by step $n - 1$ one appears in all the rows at once. The first to notice this was Pierre de Fermat.

Fermat reported it in a letter to Frénicle de Bessy of 18 October 1640 and, as was his habit, without a proof: he would have sent it, “if I did not fear being too long”. The first to publish a proof was Euler, who set it out in 1736. At the end of the last chapter the theorem came almost for free from Lagrange’s theorem. Here we’ll prove it differently, without groups, by counting necklaces. This proof was printed by Solomon Golomb in 1956, and it’s shorter than Fermat feared.

The idea: count coloured necklaces in two ways. We’ll show it with $a = 2$ colours and $p = 5$ beads; for any natural $a$ and prime $p$ the argument is the same.

Lay out $p$ beads in a row, each of one of $a$ colours. There are $a^p$ different rows: each bead has $a$ options. Here that’s $2^5 = 32$ rows. Set aside the one-colour rows, in which all the beads are the same. There are $a$ of them, and $a^p - a$ rows are left, here $30$. Tie each remaining row into a ring, a necklace. The same necklace comes from $p$ rows: the ring can be cut at any of $p$ places, which is the same as shifting the row cyclically. Group the rows by necklace. Each group has exactly $p$ different rows. If two shifts, by $i$ and by $j$ positions, gave the same row, then the shift by $s = j - i$ ($0 < s < p$) would leave the row in place, and with it the shifts by $2s, 3s, \dots$ Since $p$ is prime, $s$ is invertible modulo $p$, and among the numbers $s, 2s, 3s, \dots$ there’s one congruent to $1$. But a row unchanged by a shift of one position is one-coloured, and we set those aside. The rows that aren’t one-coloured have split into groups of $p$, so $p$ divides $a^p - a$: here $30 = 6 \cdot 5$. That’s exactly $a^p \equiv a \pmod p$ for natural $a$; for $a \le 0$ replace $a$ by a congruent natural number. If $p$ doesn’t divide $a$, then $a$ is invertible modulo $p$, and the congruence can be multiplied by $a^{-1}$: $a^{p-1} \equiv 1$. Any integer not divisible by $p$. The exponent, one less than the modulus. So in a power $a^k$ modulo a prime the exponent can be replaced by its remainder on division by $p - 1$. A prime modulus. For a composite modulus the theorem in this form is false: $2^{14} = 16{,}384 \equiv 4 \pmod{15}$. Example: $2^{100} \bmod 13$. Here $p - 1 = 12$ and $100 = 12 \cdot 8 + 4$, so $2^{100} \equiv 2^4 = 16 \equiv 3 \pmod{13}$.

How Euler proved it himself: the binomial theorem

Euler’s 1736 proof is shorter than the necklaces, but it relies on the binomial formula. Along the way we get an equation we promised to explain in chapter 7: modulo a prime, the “wrong” way of multiplying out brackets turns out to be right.

If $p$ is prime, then $(a + b)^p \equiv a^p + b^p \pmod p$ for any integers $a$ and $b$.

By the binomial formula $(a + b)^p = \sum_{k=0}^{p} \binom pk a^k b^{p-k}$. The end terms, at $k = 0$ and $k = p$, are $b^p$ and $a^p$. Let’s show that all the other coefficients $\binom pk$ for $0 < k < p$ are divisible by $p$. They’re integers, and $\binom pk \cdot k!\,(p - k)! = p!$ is divisible by $p$. The number $k!\,(p - k)!$ is a product of numbers smaller than $p$, none of them divisible by the prime $p$, so by Euclid’s lemma their product isn’t divisible by $p$ either. So by the same lemma $p$ divides $\binom pk$, and the middle terms are congruent to zero.

Now the little theorem for natural $a$, by induction on $a$. At $a = 1$ it holds: $1^p = 1$. If $a^p \equiv a$, then by the lemma $(a + 1)^p \equiv a^p + 1^p \equiv a + 1 \pmod p$. So $a^p \equiv a$ for all natural $a$, and for the other integers through a congruent natural number.

Go back to the table at $n = 7$. The row of three contains all six non-zero remainders, the row of two only three: $2, 4, 1$. The smallest $k$ for which $a^k \equiv 1$ is called the order of $a$ modulo $n$; it’s the order of an element in the group of invertible remainders from chapter 40.

Ciphers need exponents hundreds of digits long, and here the cycle won’t help: its length is huge too. What helps is something else: powers can be computed very quickly. To get $3^{100}$ you don’t need ninety-nine multiplications. Square three, square the result again, and so on: $3^2, 3^4, 3^8, 3^{16}, 3^{32}, 3^{64}$, six multiplications, taking the remainder after each so that the numbers don’t grow. And since $100 = 64 + 32 + 4$, $3^{100} = 3^{64} \cdot 3^{32} \cdot 3^4$: two more multiplications.

The exponent, written in binary (chapter 1). The one-digits of the binary expansion. Each power $a^{2^{k+1}}$ is the square of the previous $a^{2^k}$, so they’re all obtained by a chain of squarings. Example: $100 = 1100100_2 = 64 + 32 + 4$. Modulo $7$: $3^2 \equiv 2$, $3^4 \equiv 4$, $3^8 \equiv 2$, $3^{16} \equiv 4$, $3^{32} \equiv 2$, $3^{64} \equiv 4$, and $3^{100} \equiv 4 \cdot 2 \cdot 4 = 32 \equiv 4$. For an exponent of $2048$ binary digits fewer than $2 \cdot 2048$ multiplications are needed, instead of $2^{2048}$.

What remainder does $5^{2026}$ leave on division by $11$?

$11$ is prime and doesn’t divide $5$, so $5^{10} \equiv 1 \pmod{11}$. Since $2026 = 10 \cdot 202 + 6$, we get $5^{2026} \equiv 5^6$. Next: $5^2 = 25 \equiv 3$, $5^4 \equiv 3^2 = 9$, $5^6 = 5^4 \cdot 5^2 \equiv 9 \cdot 3 = 27 \equiv 5$. Answer: $5$.

A composite clock face

Fermat’s theorem is about prime moduli, while the cipher we’re heading for computes modulo a product of two primes. Look at the table of powers for $n = 15$. There are almost no ones in the last column: $2^{14} \equiv 4$. But in the column $k = 8$ there’s a one in every row where $a$ is coprime to $15$. There are eight such rows: $1, 2, 4, 7, 8, 11, 13, 14$. The rows $3, 5, 6, 9, 10, 12$ never get a one: a power of a multiple of three or five is also a multiple of three or five.

Euler was looking for the general meaning of Fermat’s little theorem and published this generalisation in 1763; for a prime $n = p$ it turns into Fermat’s theorem. The letter $\varphi$ for the function was introduced later by Gauss. Let’s prove the theorem by a permutation.

The idea: multiplying by $a$ only permutes the invertible remainders, so their product doesn’t change; on the other hand, it gets multiplied by $a^{\varphi(n)}$.

Place the invertible remainders modulo $n$ round a circle: the numbers $r_1, r_2, \dots, r_{\varphi(n)}$ from $1$ to $n - 1$ that are coprime to $n$. In the picture $n = 15$, and there are eight of them. Multiply each by $a$ and take the remainder. Again we get an invertible remainder. First, $ar$ is coprime to $n$: a common prime divisor of $ar$ and $n$ would, by Euclid’s lemma, divide $a$ or $r$. Second, the remainder on division by $n$ has the same common divisors with $n$ as the number itself: that’s the main step of the Euclidean algorithm. Different remainders go to different ones: if $ar_i \equiv ar_j$, multiply both sides by $a^{-1}$ and get $r_i \equiv r_j$. So the arrows permute the remainders: exactly one arrives at each. Multiply all the remainders together before and after the multiplication. After, they’re the same numbers in a different order, so $(ar_1)(ar_2)\cdots(ar_{\varphi(n)}) \equiv r_1 r_2 \cdots r_{\varphi(n)}$, that is, $a^{\varphi(n)} R \equiv R$, where $R$ is the product of all the $r_i$. A product of invertible remainders is invertible, so we can cancel $R$, multiplying both sides by $R^{-1}$: $a^{\varphi(n)} \equiv 1 \pmod n$. Choose another $a$: the arrows change, the conclusion doesn’t.

In the table for $n = 15$ the ones fill the coprime rows already in column $4$, earlier than the theorem promises. That happens: Euler’s theorem guarantees that the order divides $\varphi(n)$, but it doesn’t claim that it equals it.

Find the last two digits of the number $3^{2026}$, that is, its remainder on division by $100$.

First $\varphi(100)$: of the numbers from $1$ to $100$, $50$ are divisible by $2$, $20$ by $5$, $10$ by both, so exactly $100 - 50 - 20 + 10 = 40$ are coprime to $100$. By Euler’s theorem $3^{40} \equiv 1 \pmod{100}$, and $2026 = 40 \cdot 50 + 26$, so $3^{2026} \equiv 3^{26}$. Compute by fast exponentiation: $3^2 = 9$, $3^4 = 81$, $3^8 \equiv 81^2 = 6561 \equiv 61$, $3^{16} \equiv 61^2 = 3721 \equiv 21$. Since $26 = 16 + 8 + 2$, we get $3^{26} \equiv 21 \cdot 61 \cdot 9$; $21 \cdot 61 = 1281 \equiv 81$, $81 \cdot 9 = 729 \equiv 29$. Answer: $29$.

Sunzi’s problem

The Chinese treatise Sunzi Suanjing (The Mathematical Classic of Sunzi, 3rd–5th centuries) has a problem: “There are things whose number is unknown. Counted by threes, two are left over; by fives, three; by sevens, two. How many things are there?” The answer is given there too: $23$. In the language of congruences we need an $x$ with $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$ and $x \equiv 2 \pmod 7$.

You can search by trial, and cleverly. Write out the numbers with remainder $2$ modulo $7$: $2, 9, 16, 23, \dots$, and check the other conditions. The number $23$ leaves remainder $3$ on division by $5$ and remainder $2$ on division by $3$. Found it. But is there always a solution? And how many?

Wheels of $3$, $5$ and $7$ divisions return to their starting position only after $3 \cdot 5 \cdot 7 = 105$ steps, and in these $105$ steps every combination of remainders occurs exactly once. With wheels of $4$ and $6$ divisions it’s different: they line up again after just $12$ steps, but there are $24$ combinations, and half of them never appear. It all depends on the common divisor.

The idea: lay out the numbers from $0$ to $mn - 1$ in a table where the row is the remainder modulo $m$ and the column the remainder modulo $n$, and see that each cell is occupied by exactly one number.

Take a table of $m$ rows and $n$ columns. Put the number $x$ in row $x \bmod m$ and column $x \bmod n$. Going from $x$ to $x + 1$ is a step one cell down and one to the right, and going off the edge of the table we come back from the opposite side, like the letters on Caesar’s wheel. Two different numbers from $0$ to $mn - 1$ don’t land in the same cell. Let $x \equiv y \pmod m$ and $x \equiv y \pmod n$. Then $x - y = mk$ for some integer $k$, and $n$ divides $mk$. Since $n$ is coprime to $m$, by the generalised Euclid’s lemma $n$ divides $k$, and $mn$ divides $x - y$. But the difference of two numbers from $0$ to $mn - 1$ is less than $mn$ in absolute value, so $x = y$. The path first returns to the cell of the number $0$ only at step $mn$. There are exactly $mn$ numbers from $0$ to $mn - 1$, and $mn$ cells too, and no two numbers share a cell. So all the cells are occupied: for any pair of remainders $(r, s)$ there’s a number $x$. Existence is proved. Uniqueness is the second step: two solutions with the same remainders modulo $m$ and modulo $n$ differ by a multiple of $mn$. Change the size of the table: as long as $m$ and $n$ are coprime, the path goes through every cell. With a common divisor, say $4$ and $6$, it would close up after $\operatorname{lcm}(4, 6) = 12$ steps without filling even half the table.

For three or more pairwise coprime moduli the theorem holds just the same: first combine the first two congruences into one modulo $mn$, then that with the third, and so on. A general method for solving such systems was set out by Qin Jiushao in his Mathematical Treatise in Nine Sections (1247). Sunzi’s treatise itself does without trial: it assembles the answer from ready-made parts.

The required remainder modulo $m$. A part that’s congruent to $1$ modulo $m$ and to $0$ modulo $n$: it’s a multiple of $n$, and the factor $n^{-1}$ makes it one modulo $m$. The inverse exists because $m$ and $n$ are coprime. The required remainder modulo $n$. The part the other way round: congruent to $0$ modulo $m$ and to $1$ modulo $n$. Sunzi’s example, with three moduli. The part $70$ leaves remainder $1$ on division by $3$ and is divisible by $5$ and $7$; the part $21$ is congruent to $1$ modulo $5$ and divisible by $3$ and $7$; the part $15$ is congruent to $1$ modulo $7$ and divisible by $3$ and $5$. The answer: $2 \cdot 70 + 3 \cdot 21 + 2 \cdot 15 = 233 \equiv 23 \pmod{105}$. That’s exactly how it’s solved in the treatise, $140$, $63$, $30$, $233$ in all, minus $210$, and later the numbers $70$, $21$ and $15$ were even put into a Chinese rhyme.

The Chinese remainder theorem gives a formula for Euler’s function straight away. A number is invertible modulo $mn$ exactly when it’s invertible both modulo $m$ and modulo $n$, and in the table such numbers occupy particular rows and columns.

The idea: in the table of the Chinese remainder theorem the numbers coprime to $mn$ fill a $\varphi(m) \times \varphi(n)$ rectangle.

Again lay out the numbers from $0$ to $mn - 1$ in an $m \times n$ table. By the Chinese remainder theorem each stands in its own cell, and all the cells are occupied. A number $x$ is coprime to $m$ if and only if its remainder $x \bmod m$ is coprime to $m$: they have the same common divisors with $m$. Mark the rows whose numbers are coprime to $m$. There are $\varphi(m)$ of them. Likewise mark the columns whose numbers are coprime to $n$. There are $\varphi(n)$ of them. A number is coprime to $mn$ if and only if it’s coprime to both $m$ and $n$: a common prime divisor with $mn$ divides $m$ or $n$ by Euclid’s lemma. Such numbers stand exactly at the intersections of the marked rows and columns. There are $\varphi(m)\,\varphi(n)$ intersections, with exactly one number in each. So $\varphi(mn) = \varphi(m)\,\varphi(n)$. For primes $p \ne q$ all the rows except the zero one are marked, and all the columns except the zero one: $\varphi(pq) = (p - 1)(q - 1)$.

It remains to compute $\varphi$ for a prime power. Among the numbers from $1$ to $p^k$ only the multiples of $p$ aren’t coprime to $p^k$: $p, 2p, \dots, p^{k-1} \cdot p$, and there are $p^{k-1}$ of them. So $\varphi(p^k) = p^k - p^{k-1} = p^k\left(1 - \frac1p\right)$. Factor $n$ into powers of distinct primes, apply multiplicativity, and we get the general formula.

A natural number with the factorisation $n = p_1^{k_1} p_2^{k_2} \cdots p_s^{k_s}$ into powers of distinct primes. One factor for each prime in $n$: each prime sieves out its own share $\frac1p$ of the numbers, and the shares don’t interfere with one another; that’s what multiplicativity means. The exponents $k_i$ don’t appear in the formula. Example: $360 = 2^3 \cdot 3^2 \cdot 5$, and $\varphi(360) = 360 \cdot \frac12 \cdot \frac23 \cdot \frac45 = 96$. A check in parts: $\varphi(8)\,\varphi(9)\,\varphi(5) = 4 \cdot 6 \cdot 4 = 96$.

An old problem. A market woman carries a basket of eggs. If she takes them out in $2$s, $3$s, $4$s, $5$s or $6$s, one egg is left each time, and if in $7$s, none is left. What’s the smallest number of eggs the basket can hold?

The conditions about $2, 3, 4, 5, 6$ mean that $x - 1$ is divisible by each of these numbers, that is, by their lcm, which is $60$: $x \equiv 1 \pmod{60}$. Besides, $x \equiv 0 \pmod 7$. The numbers $60$ and $7$ are coprime, so the solution is unique modulo $420$. Try $1, 61, 121, 181, 241, 301$: only $301 = 7 \cdot 43$ is divisible by $7$. Answer: $301$ eggs.

Before building the locks, practise computing modulo $n$: remainders, inverses, large powers and systems. The congruence solver will take any such problem apart step by step.

A secret said out loud

All the ciphers so far have been symmetric: one key encrypts and decrypts, and both sides must know it in advance. Keys have to be delivered, and in the twentieth century this became a huge business: one-time pads were carried by diplomatic bag and by courier. In 1976 Whitfield Diffie and Martin Hellman published the paper New Directions in Cryptography and showed how two people can agree on a shared secret while talking only in the open.

Let’s do it with paints first. Alice and Bob publicly choose a common paint, say yellow. Each mixes a secret paint, shown to no one, into their own portion of yellow and sends the mixture to the other, openly, for everyone to see. On receiving the other’s mixture, each adds their own secret paint to it. Now both have all three paints in their pot, the yellow and the two secret ones, and the colour comes out the same. Eve saw the yellow and both mixtures, but she can’t separate a mixture back into its components. And if she pours the two mixtures together, there’ll be twice as much yellow, and the colour will be different.

With numbers, the paints are mixed by raising to a power modulo a prime. A large prime $p$ and a number $g$, a primitive root modulo $p$, are chosen openly. Alice thinks of a secret number $a$ and sends $A = g^a \bmod p$. Bob thinks of $b$ and sends $B = g^b \bmod p$. Alice computes $B^a$, Bob $A^b$, and both get the same thing, because $(g^b)^a = g^{ab} = (g^a)^b$.

The secret exponents of Alice ($a$) and Bob ($b$). Nobody passes them to anyone. The public numbers $A = g^a \bmod p$ and $B = g^b \bmod p$: the “mixtures” that Eve sees. The shared secret. Both compute it, but it’s never said out loud. Example: $p = 23$, $g = 5$. Alice takes $a = 6$ and sends $A = 5^6 \bmod 23 = 8$; Bob takes $b = 15$ and sends $B = 5^{15} \bmod 23 = 19$. Alice computes $19^6 \bmod 23 = 2$, Bob $8^{15} \bmod 23 = 2$. The shared secret is $2$.

Eve knows $p$, $g$, $A$ and $B$. To get the secret, it’s enough for her to find $a$ from $A = g^a \bmod p$.

Raising to a power modulo $p$ is easy, by fast exponentiation. Finding the exponent from the result is, as far as anyone knows, hard. For a prime modulus of $2048$ binary digits the best known algorithms need on the order of $2^{112} \approx 5 \cdot 10^{33}$ operations, work beyond all the computers on Earth put together. Functions that are easy to compute and hard to invert are called one-way. Nobody has proved that they exist at all: their existence would imply $\mathrm P \ne \mathrm{NP}$, one of the main open problems of mathematics. All of modern cryptography stands on an honest “nobody knows how yet”.

The protocol needs a primitive root $g$: then $A = g^a$ can be any non-zero remainder, and Eve has nothing to grab hold of. In the Disquisitiones Arithmeticae Gauss gave two proofs that one always exists.

The proof: how many remainders have each order

The idea: count how many non-zero remainders have each possible order, and see that the order $p - 1$ can’t be left empty. We’ll need three facts.

First: if $a^m \equiv 1$, then the order $d$ of $a$ divides $m$. Divide with remainder: $m = dq + r$, $0 \le r < d$. Then $1 \equiv a^m = (a^d)^q a^r \equiv a^r$. Since $d$ is the smallest positive exponent giving one and $r < d$, we have $r = 0$. In particular, by Fermat’s little theorem the order of any non-zero remainder divides $p - 1$.

Second: the congruence $x^d \equiv 1 \pmod p$ has at most $d$ solutions among the remainders. This is the theorem on the number of roots from chapter 14, and its proof works for remainders modulo a prime almost word for word. The one place that needs care is the conclusion “$(b - a)Q(b) = 0$ and $b \ne a$, so $Q(b) = 0$”. Modulo $p$ it holds by Euclid’s lemma: if $p$ divides $(b - a)Q(b)$ and doesn’t divide $b - a$, then $p$ divides $Q(b)$.

Third: for each divisor $d$ of $p - 1$ there are either no remainders of order $d$ at all, or exactly $\varphi(d)$. Let $a$ have order $d$. The numbers $1, a, a^2, \dots, a^{d-1}$ are distinct (if $a^i \equiv a^j$ with $0 \le i < j < d$, then $a^{j - i} \equiv 1$ too early) and all satisfy $x^d \equiv 1$. By the second fact there are no other solutions, so each remainder of order $d$ is one of the powers $a^j$, $0 \le j < d$. The order of $a^j$ is $d$ exactly when $\gcd(j, d) = 1$. Indeed, if $\gcd(j, d) = g > 1$, then $(a^j)^{d/g} = (a^d)^{j/g} \equiv 1$ too early. And if $\gcd(j, d) = 1$ and $(a^j)^k \equiv 1$, then by the first fact $d$ divides $jk$, and so, by the generalised Euclid’s lemma, divides $k$. There are exactly $\varphi(d)$ such $j$.

The count. Let $\psi(d)$ be the number of remainders of order $d$. Each of the $p - 1$ non-zero remainders has some order dividing $p - 1$, so the sum of $\psi(d)$ over all divisors $d$ of $p - 1$ is $p - 1$. On the other hand, the sum of $\varphi(d)$ over all divisors $d$ of any natural number $N$ is $N$. To see this, reduce the fractions $\frac1N, \frac2N, \dots, \frac NN$: after reduction the denominator $d$ is a divisor of $N$, and the denominator $d$ is obtained by exactly $\varphi(d)$ fractions, namely the fractions $\frac kd$ with $1 \le k \le d$ and $\gcd(k, d) = 1$. For $N = p - 1$ the two sums are equal, and by the third fact each term of the first is at most the corresponding term of the second. So $\psi(d) = \varphi(d)$ for all $d$, and in particular $\psi(p - 1) = \varphi(p - 1) \ge 1$. A remainder of order $p - 1$ exists: that’s a primitive root.

A lock anyone can snap shut

Key exchange solves half the problem: Alice and Bob get a shared secret, but both have to be online at the same time. Diffie and Hellman dreamed of more: public-key encryption. Picture a letterbox with a slot: anyone can drop a letter in, but only the owner of the key can take it out. For a cipher this means that the encryption key can be published and anyone can encrypt a letter with it, but only the owner of a second, private key can decrypt it. A year after Diffie and Hellman’s paper, three researchers at the Massachusetts Institute of Technology, Ronald Rivest, Adi Shamir and Leonard Adleman, found such a lock. The cipher was named after their initials: RSA.

The recipe for the keys. Alice chooses two large primes $p$ and $q$ and keeps them secret. She publishes their product $n = pq$ and a number $e$ coprime to $\varphi(n) = (p - 1)(q - 1)$. She keeps for herself $d$, the inverse of $e$ modulo $\varphi(n)$; the extended Euclidean algorithm provides it. A message is a number $m$ from $0$ to $n - 1$.

The message: a number from $0$ to $n - 1$. Text is first turned into numbers. The public exponent. In practice $e = 65{,}537 = 2^{16} + 1$ is often taken: it’s prime, and raising to it is fast. The public modulus $n = pq$. Anyone may know it; the secret is that nobody but Alice knows $p$ and $q$. The ciphertext. It can be sent in the open. The private exponent. To compute it you need to know $\varphi(n) = (p - 1)(q - 1)$, and for that the factorisation of $n$. Example: $p = 61$, $q = 53$, $n = 3233$, $\varphi(n) = 60 \cdot 52 = 3120$, $e = 17$, $d = 2753$ (check: $17 \cdot 2753 = 46{,}801 = 15 \cdot 3120 + 1$). The message $m = 65$ is encrypted as $c = 65^{17} \bmod 3233 = 2790$, and $2790^{2753} \bmod 3233 = 65$.

In the lab letters are encrypted in pairs: a pair turns into the number $27x + y$, where $x$ and $y$ are the letters’ numbers (a space is zero, A is one). If letters were encrypted one at a time, identical letters would give identical numbers, and al-Kindi’s frequency analysis would work against RSA too. Real RSA goes further: before encryption random bytes are mixed into the message, so that even the same letter sent twice gives different ciphertexts.

Eve knows $n = 3233$ and $e = 17$. If she factors $n$, she’ll learn $p$ and $q$, compute $\varphi(n)$, and from that $d$, by the same extended Euclidean algorithm as Alice. For $3233$ trying divisors up to $\sqrt{3233} \approx 57$ is enough; in the lab it’s one press of a button. The whole security of RSA rests on the fact that with numbers hundreds of digits long this doesn’t work.

A toy key: $p = 5$, $q = 11$, $e = 3$. Find the private exponent $d$, a number from $1$ to $\varphi(n) - 1$.

$n = 55$, $\varphi(n) = 4 \cdot 10 = 40$. We need $3d \equiv 1 \pmod{40}$. Since $40 = 13 \cdot 3 + 1$, we have $3 \cdot (-13) \equiv 1$ and $d \equiv -13 \equiv 27$. Check: $3 \cdot 27 = 81 = 2 \cdot 40 + 1$. The message $m = 7$ is encrypted as $7^3 = 343 \equiv 13 \pmod{55}$, and $13^{27} \bmod 55$ gives $7$ again.

RSA can be used not only to encrypt but also to sign. Alice raises the message to her private power $d$, and anyone can check the signature by raising the result to the public power $e$: if the original message comes out, only the owner of $d$ could have signed it. That’s how a bank’s server proves it’s the real one.

Breaking in

Factoring a number is a problem people have wrestled with for more than two thousand years, and there’s still no fast way to do it. Trying divisors up to $\sqrt n$ for a number of $617$ digits (that’s how many there are in an RSA-2048 key) would take on the order of $10^{308}$ divisions. The best known method, the number field sieve, is far cleverer than trial division, but its running time too grows faster than any power of the number of digits. The current record is RSA-250, a number of $250$ digits, or $829$ binary digits. It was factored in February 2020; the computation took about $2700$ years of work on a single processor core, spread over thousands of machines.

A threat of another kind appeared in 1994: Peter Shor devised an algorithm for a quantum computer that factors numbers and finds discrete logarithms in a time that grows only as a power of the number of digits. The quantum part of the algorithm finds the order of a number $a$ modulo $n$, the very period of a row in our table of powers. After that ordinary modular arithmetic takes over. If the order $r$ is even, then $n$ divides $a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1)$, and often the common divisor of $n$ with one of the brackets turns out to be non-trivial. For $n = 15$ and $a = 7$: the order of seven is $4$, $7^2 = 49 \equiv 4$, and $\gcd(4 - 1, 15) = 3$, $\gcd(4 + 1, 15) = 5$. Quantum computers able to factor a real key don’t exist yet, but nobody wants to wait for them: a ciphertext recorded today could be read in twenty years.

So in August 2024 the US standards institute NIST approved the first post-quantum standards: FIPS 203 (the key-agreement mechanism ML-KEM), FIPS 204 and FIPS 205 (the digital signatures ML-DSA and SLH-DSA). The first two are built on lattice problems, about short vectors in multidimensional grids of points, and the third on hash functions. No fast quantum algorithms for these problems are known. Post-quantum key agreement already works in browsers, paired with a classical one: if one of the two locks is ever broken, the other will keep holding.

When you open your bank’s website, the browser and the server first agree on a shared secret by the Diffie–Hellman scheme: they exchange “mixtures” in the open, and an eavesdropper can’t compute the key unless they learn to find discrete logarithms. Today this exchange is more often done on elliptic curves (about them, chapter 44), and increasingly together with the post-quantum ML-KEM. To make sure you’re talking to the bank and not to Eve in the middle, the server signs its part of the conversation, and the signature is checked with the public key from its certificate: that’s RSA, or a signature on the same curves. The data themselves are then encrypted by a fast symmetric cipher, usually AES, with a key derived from the shared secret. The security of the whole construction rests on the difficulty of two problems of number theory: factorisation and the discrete logarithm.

Where next

Throughout the chapter we used one property of a prime modulus: in $\mathbb Z_p$ you can divide by any non-zero number. Remainders modulo a prime add, subtract, multiply and divide like fractions, although there are only $p$ of them. In $\mathbb Z_6$ that’s impossible: $2 \cdot 3 = 0$, although neither $2$ nor $3$ is zero, and you can’t divide by them. What other systems of “numbers” can do all four operations? Can such a system be built from exactly four elements, if $\mathbb Z_4$ won’t do ($2 \cdot 2 = 0$)? It can, and such systems are what the codes that correct errors in QR codes, on CDs and in signals from distant space probes run on, and so does the AES cipher that guards data once the key has been agreed. That’s the subject of the next chapter.