Fermat, Euler and RSA

Powers modulo a prime return to $1$ on a fixed rhythm, and the problem is to explain that rhythm well enough to compute enormous powers in a handful of steps and to build a secret code on them.

The previous lesson made remainders into a number system and ended by noticing that powers in it repeat. This lesson uses two of its results: $[a]$ has an inverse modulo $n$ exactly when $\gcd (a, n) = 1$ , found by running Euclid's algorithm backwards, and the Chinese remainder theorem, by which a number modulo $p q$ is determined by its remainders modulo $p$ and $q$ . It also uses Euler's totient $φ (n)$ from an earlier lesson, the count of integers from $1$ to $n$ coprime to $n$ (the letter $φ$ here is the totient again, not the golden ratio it stood for in the lesson on linear recurrences).

Powers modulo a prime

Here are the powers of every non-zero class modulo $7$ , each entry the previous one times $a$ , reduced.

$a$	$a^{1}$	$a^{2}$	$a^{3}$	$a^{4}$	$a^{5}$	$a^{6}$
1	1	1	1	1	1	1
2	2	4	1	2	4	1
3	3	2	6	4	5	1
4	4	2	1	4	2	1
5	5	4	6	2	3	1
6	6	1	6	1	6	1

The last column is all $1$ s: every $a$ not divisible by $7$ has $a^{6} \equiv 1 (mod 7)$ . And each row returns to $1$ for the first time after $1$ , $3$ , $6$ , $3$ , $6$ or $2$ steps, all divisors of $6$ . The powers of $2$ cycle through $2, 4, 1$ , while those of $3$ and $5$ pass through every non-zero class before coming home.

Modulo $11$ likewise $2^{10} = 1024 = 93 \times 11 + 1$ . For a composite the obvious analogue fails: $3^{9} = 19 683 \equiv 3 (mod 10)$ , not $1$ .

Fermat's little theorem

Pierre de Fermat stated the pattern, without proof, in a letter to Bernard Frénicle de Bessy dated 18 October 1640. Leibniz wrote one down in unpublished notes before 1683, and Euler published the first in 1736.

Theorem (Fermat). If $p$ is prime and $p$ does not divide $a$ , then $a^{p - 1} \equiv 1 (mod p)$ .

Consider the $p - 1$ numbers $a, 2 a, 3 a, \dots, (p - 1) a$ . None is $\equiv 0 (mod p)$ , since by Euclid's lemma a prime dividing $k a$ divides $k$ or $a$ , and it divides neither. No two are congruent either: if $i a \equiv j a$ , multiply both sides by the inverse of $a$ , which exists because $\gcd (a, p) = 1$ , to get $i \equiv j$ . So they are the classes $1, 2, \dots, p - 1$ in some order, and multiplying all of them together both ways gives

a \times 2 a \times \dots \times (p - 1) a \equiv 1 \times 2 \times \dots \times (p - 1) (mod p)

The left side is $a^{p - 1} (p - 1)!$ . Every factor of $(p - 1)!$ is coprime to $p$ , so $(p - 1)!$ is invertible modulo $p$ , and cancelling it leaves $a^{p - 1} \equiv 1$ . For $p = 7$ and $a = 3$ the products $3, 6, 9, 12, 15, 18$ reduce to $3, 6, 2, 5, 1, 4$ , a shuffle of $1$ to $6$ , exactly as the proof says.

Multiplying by $a$ gives $a^{p} \equiv a (mod p)$ , true for every integer $a$ , since when $p ∣ a$ both sides are $0$ . The converse is false. The composite $341 = 11 \times 31$ satisfies $2^{340} \equiv 1 (mod 341)$ , and $561 = 3 \times 11 \times 17$ satisfies $a^{560} \equiv 1$ for every $a$ coprime to it, the first of the numbers Robert Carmichael described in 1910. Failing the test does prove compositeness: $2^{90} \equiv 64 (mod 91)$ , so $91$ is not prime, and no factor was needed to show it.

Euler's generalisation

Modulo $10$ the powers of $3$ run $3, 9, 7, 1$ , back to $1$ after four steps, and $4 = φ (10)$ , counting $1, 3, 7, 9$ . Fermat's proof used only that multiplying by $a$ keeps the classes $1, \dots, p - 1$ distinct and non-zero, and that their product can be cancelled. Modulo a composite $n$ the classes coprime to $n$ behave the same way, and Euler saw in 1763 that the proof goes through.

Theorem (Euler). If $\gcd (a, n) = 1$ , then $a^{φ (n)} \equiv 1 (mod n)$ .

The proof is Fermat's with new classes. Let $r_{1}, \dots, r_{φ (n)}$ be the integers from $1$ to $n$ coprime to $n$ . Each $a r_{i}$ is coprime to $n$ too, since a prime dividing $n$ and $a r_{i}$ would divide $a$ or $r_{i}$ . The products are distinct modulo $n$ , since $a$ is invertible. So they are the $r_{i}$ reshuffled, and multiplying everything gives $a^{φ (n)} R \equiv R$ , where $R$ is the product of the $r_{i}$ . Being coprime to $n$ , $R$ cancels. Modulo $10$ with $a = 3$ , the products $3, 9, 21, 27$ reduce to $3, 9, 1, 7$ , the same four classes shuffled.

For a prime, $φ (p) = p - 1$ and Euler's theorem is Fermat's. The formula from inclusion and exclusion, $φ (n) = n$ times $1 - \frac{1}{p}$ for each prime $p$ dividing $n$ , supplies the exponent: $φ (100) = 100 \times \frac{1}{2} \times \frac{4}{5} = 40$ , and for distinct primes $φ (p q) = (p - 1) (q - 1)$ .

The hypothesis $\gcd (a, n) = 1$ cannot be dropped: powers of $2$ are even, so none is $\equiv 1 (mod 10)$ . And $φ (n)$ is an exponent that always works, not always the smallest: modulo $100$ , $3^{20}$ is already $\equiv 1$ .

Reducing huge exponents

If $a^{m} \equiv 1 (mod n)$ , powers of $a$ repeat with period $m$ : writing $k = m q + s$ with $0 \leq s < m$ gives

a^{k} = (a^{m})^{q} a^{s} \equiv 1^{q} a^{s} = a^{s} (mod n)

Euler's theorem always provides such an $m$ , namely $φ (n)$ . The base is reduced modulo $n$ and the exponent modulo $φ (n)$ , and confusing the two is the commonest error here.

The last digit of a number is its remainder modulo $10$ . For $3^{2026}$ , with $φ (10) = 4$ and $2026 = 4 \times 506 + 2$ , the last digit is that of $3^{2}$ , which is $9$ .

Example. Find the last two digits of $3^{2026}$ .

Work modulo $100$ , where $\gcd (3, 100) = 1$ and $φ (100) = 40$ . Since $2026 = 40 \times 50 + 26$ , the task is $3^{26} (mod 100)$ . Build it up: $3^{5} = 243 \equiv 43$ , then $3^{10} \equiv 43^{2} = 1849 \equiv 49$ , then $3^{20} \equiv 49^{2} = 2401 \equiv 1$ . So in fact the period is $20$ , and $3^{26} \equiv 3^{6} = 729 \equiv 29$ . The last two digits are $29$ .

Now you. Find the last two digits of $13^{2026}$ .

Answer

Again reduce the exponent modulo $40$ : the task is $13^{26} (mod 100)$ . Then $13^{2} = 169 \equiv 69$ , $13^{4} \equiv 69^{2} = 4761 \equiv 61$ , $13^{5} \equiv 61 \times 13 = 793 \equiv 93$ , $13^{10} \equiv 93^{2} = 8649 \equiv 49$ and $13^{20} \equiv 49^{2} \equiv 1$ . So $13^{26} \equiv 13^{6} = 13^{4} \times 13^{2} \equiv 61 \times 69 = 4209 \equiv 9$ , and the last two digits are $09$ .

Repeated squaring

Reducing the exponent needs $φ (n)$ , and RSA needs $a^{k} (mod n)$ with $k$ hundreds of digits long, and multiplying by $a$ one step at a time would take $k - 1$ multiplications, more than there are atoms in the universe. Squaring doubles the exponent with each multiplication, $a^{2}$ , $a^{4} = (a^{2})^{2}$ , $a^{8}$ and so on, reduced modulo $n$ each time. Any exponent is a sum of powers of $2$ , its binary expansion, so multiply together the squares matching its $1$ bits.

An exponent with $b$ binary digits needs $b - 1$ squarings, and if it has $w$ ones, $w - 1$ further multiplications to combine them: at most $2 (b - 1)$ in all. For a $2048$ bit exponent, around $10^{616}$ in size, that is at most $4094$ multiplications.

Example. Compute $3^{100} (mod 101)$ by repeated squaring, and count the multiplications.

In binary $100 = 1100100_{2} = 64 + 32 + 4$ . Square six times, reducing modulo $101$ : $3^{2} = 9$ , $3^{4} = 81$ , $3^{8} \equiv 81^{2} = 6561 \equiv 97$ , $3^{16} \equiv 97^{2} \equiv (- 4)^{2} = 16$ , $3^{32} \equiv 256 \equiv 54$ , $3^{64} \equiv 54^{2} = 2916 \equiv 88$ . Then combine: $3^{64} \times 3^{32} \equiv 88 \times 54 = 4752 \equiv 5$ , and $5 \times 3^{4} = 405 \equiv 1$ . So $3^{100} \equiv 1$ , in $6 + 2 = 8$ multiplications instead of $99$ , as Fermat predicts for the prime $101$ .

Now you. Compute $5^{45} (mod 101)$ by repeated squaring, and count the multiplications.

Answer

$45 = 101101_{2} = 32 + 8 + 4 + 1$ . The squares are $5^{2} = 25$ , $5^{4} = 625 \equiv 19$ , $5^{8} \equiv 361 \equiv 58$ , $5^{16} \equiv 3364 \equiv 31$ , $5^{32} \equiv 961 \equiv 52$ . Then $52 \times 58 = 3016 \equiv 87$ , $87 \times 19 = 1653 \equiv 37$ and $37 \times 5 = 185 \equiv 84$ . So $5^{45} \equiv 84$ , in $5 + 3 = 8$ multiplications.

The RSA cryptosystem

Every cipher before 1976 needed a key agreed in secret, since whoever could lock could unlock. That year Whitfield Diffie and Martin Hellman proposed separating the two: a public key anyone can use to encrypt, and a private key that only its owner uses to decrypt. Ron Rivest, Adi Shamir and Leonard Adleman at MIT found a way to do it in 1977, named RSA from their initials. Clifford Cocks at GCHQ, the British signals intelligence agency, had found the same system in 1973, but it stayed classified until 1997.

To make keys, choose two primes $p$ and $q$ and let $n = p q$ , so $φ (n) = (p - 1) (q - 1)$ . Choose an exponent $e$ coprime to $φ (n)$ , and compute its inverse $d$ modulo $φ (n)$ with extended Euclid, so that $e d \equiv 1 (mod φ (n))$ . Publish $(n, e)$ and keep $d$ secret. A message is a number $0 \leq m < n$ . Anyone encrypts it as $c \equiv m^{e} (mod n)$ , and the key holder decrypts by computing $c^{d} (mod n)$ , which will turn out to be $m$ .

The classic small key takes $p = 61$ and $q = 53$ . Then $n = 3233$ and $φ (n) = 60 \times 52 = 3120$ . Take $e = 17$ , which is prime and does not divide $3120$ . Euclid's algorithm runs $3120 = 183 \times 17 + 9$ , $17 = 1 \times 9 + 8$ , $9 = 1 \times 8 + 1$ , and backwards

1 = 9 - 8 = 2 \times 9 - 17 = 2 \times 3120 - 367 \times 17

so $17^{- 1} \equiv - 367 \equiv 2753 (mod 3120)$ . Check: $17 \times 2753 = 46 801 = 15 \times 3120 + 1$ . The public key is $(3233, 17)$ and the private key is $d = 2753$ .

Example. Encrypt the message $m = 65$ with the public key $(3233, 17)$ , and decrypt it.

Here $17 = 10001_{2} = 16 + 1$ , so square four times modulo $3233$ : $65^{2} = 4225 \equiv 992$ , $65^{4} \equiv 992^{2} \equiv 1232$ , $65^{8} \equiv 1232^{2} \equiv 1547$ and $65^{16} \equiv 1547^{2} \equiv 789$ . Then $c \equiv 789 \times 65 = 51 285 \equiv 2790$ , in five multiplications. Decryption computes $2790^{2753} (mod 3233)$ . In binary $2753 = 101011000001_{2}$ , twelve digits with five ones, so it takes $11$ squarings and $4$ multiplications, and the result is $65$ again.

Now you. Build a key from $p = 7$ and $q = 13$ with $e = 5$ . Find $d$ , encrypt $m = 10$ , and decrypt the result.

Answer

$n = 91$ and $φ (n) = 72$ . Euclid gives $72 = 14 \times 5 + 2$ and $5 = 2 \times 2 + 1$ , so $1 = 5 - 2 \times (72 - 14 \times 5) = 29 \times 5 - 2 \times 72$ and $d = 29$ . To encrypt: $10^{2} = 100 \equiv 9$ , $10^{4} \equiv 81$ , $10^{5} \equiv 810 \equiv 82$ , so $c = 82$ . To decrypt, $29 = 16 + 8 + 4 + 1$ and the squares of $82$ are $82^{2} \equiv 81$ , $82^{4} \equiv 9$ , $82^{8} \equiv 81$ , $82^{16} \equiv 9$ . Then $9 \times 81 = 729 \equiv 1$ , $1 \times 9 = 9$ and $9 \times 82 = 738 \equiv 10$ , the message.

Why decryption works

Since $e d \equiv 1 (mod φ (n))$ , write $e d = 1 + k φ (n)$ for some integer $k \geq 0$ . Decrypting computes $c^{d} \equiv (m^{e})^{d} = m^{e d}$ , and when $\gcd (m, n) = 1$ Euler's theorem finishes it:

m^{e d} = m \times {(m^{φ (n)})}^{k} \equiv m \times 1^{k} = m (mod n)

Since $0 \leq m < n$ , the remainder is $m$ itself. For the key above, $e d = 46 801 = 1 + 15 \times 3120$ .

If $m$ shares a factor with $n$ , Euler's theorem says nothing, and the Chinese remainder theorem steps in: check modulo $p$ and $q$ separately. Suppose $p ∣ m$ but $q$ does not. Modulo $p$ both $m^{e d}$ and $m$ are $0$ . Modulo $q$ , Fermat gives $m^{q - 1} \equiv 1$ , and $e d = 1 + k (p - 1) (q - 1)$ , so $m^{e d} = m \times (m^{q - 1})^{k (p - 1)} \equiv m$ . The two numbers agree modulo $p$ and modulo $q$ , so by the uniqueness half of the theorem they agree modulo $p q = n$ . (If both primes divide $m$ , then $m = 0$ .) With the key above, $m = 61$ encrypts to $610$ , and $610^{2753} \equiv 61 (mod 3233)$ .

Secure only while factoring is hard

An attacker sees $n$ , $e$ and $c$ . The route to $d$ is through $φ (n)$ , and finding $φ (n)$ is exactly as hard as factoring $n$ . The primes give $(p - 1) (q - 1)$ , and conversely $φ (n) = p q - (p + q) + 1$ , so knowing it gives $p + q = n - φ (n) + 1$ , and with $p q = n$ the primes are the roots of $t^{2} - (p + q) t + n = 0$ . For the toy key, $p + q = 3233 - 3120 + 1 = 114$ , and $t^{2} - 114 t + 3233 = 0$ has roots $61$ and $53$ .

Multiplying two primes takes an instant, and no known method on an ordinary computer undoes it in time polynomial in the number of digits. That asymmetry is the whole lock. The best general method, the number field sieve, factored RSA-250, a 250 digit (829 bit) challenge number, in February 2020, after roughly 2700 core-years of computation by Fabrice Boudot, Paul Zimmermann and four colleagues. Recommended keys are $2048$ bits and up, $617$ digits or more, far beyond that reach. Nobody has proved that factoring is hard, so the security is an empirical bet, and in 1994 Peter Shor gave an algorithm that factors in polynomial time on a large quantum computer, which no machine built so far is anywhere near big enough to run.

The integers are one kind of discrete structure, rich enough to protect the traffic of the internet. Another is the network (cities and roads, bridges over a river, people and friendships), where all that matters is what is joined to what, and the next lesson models it with graphs.