Number Theory & Cryptography¶
Here is the good news about this entire topic: almost everything follows from one algorithm. The Euclidean algorithm computes the greatest common divisor of two numbers, and — run backwards — it writes that gcd as a combination of them. That single trick solves diophantine equations, produces modular inverses, and generates RSA keys. Learn it cold and most of this chapter falls out.
The Euclidean algorithm¶
The goal. Find \(\gcd(n, m)\), the largest integer dividing both \(n\) and \(m\).
The method. Repeatedly replace the bigger number by its remainder when divided by the smaller. Keep going until the remainder hits \(0\); the last nonzero remainder is the gcd.
Why it works (the one-line reason). Any common divisor of \(n\) and \(m\) also divides their remainder \(n \bmod m\) — so at every step the set of common divisors is unchanged. The numbers shrink but their gcd doesn't, and when one hits \(0\), the gcd is just the other number.
Writing the gcd as a combination¶
This is the part that does all the downstream work.
Bézout's identity
The gcd can always be written as an integer combination of the two numbers:
You find \(x\) and \(y\) by running the algorithm forward, then back-substituting through the division steps to unwind the gcd in terms of the originals. This is the extended Euclidean algorithm. It's mechanical once you've done it a few times — practise until it is.
Worked slowly: \(\gcd(15, 17)\) as a combination
Forward (divide, record the remainder, repeat):
The last nonzero remainder is \(1\), so \(\gcd(15, 17) = 1\).
Backward — start from the line whose remainder is the gcd, and substitute each earlier remainder in turn. Begin at \(15 = 7 \cdot 2 + 1\), i.e. isolate the \(1\):
Now the previous line says \(2 = 17 - 15\). Substitute that in, then collect the \(15\)'s and \(17\)'s:
So \(x = 8\), \(y = -7\). Check: \(15 \cdot 8 + 17 \cdot(-7) = 120 - 119 = 1\). ✓
The rhythm is always the same: isolate the gcd, then repeatedly replace the most-recent remainder using the line above it, keeping everything in terms of the two original numbers.
Linear diophantine equations¶
A diophantine equation is one where solutions must be integers — no fractions allowed. The linear kind looks like \(ax + by = c\).
First question: does it even have a solution? Notice the left side \(ax + by\) is always a multiple of \(\gcd(a,b)\) (since that gcd divides both \(a\) and \(b\)). So if \(\gcd(a,b)\) does not divide \(c\), there's no hope. Remarkably, that's the only obstruction:
Solvability criterion
\(ax + by = c\) has integer solutions if and only if \(\gcd(a, b) \mid c\).
The recipe¶
- Compute \(d = \gcd(a, b)\) with the Euclidean algorithm. If \(d \nmid c\), stop — there are no solutions.
- Use the extended algorithm to write \(d = ax_0' + by_0'\).
- Scale up by \(c/d\) to get one actual solution \((x_0, y_0)\) of \(ax + by = c\).
- Get all solutions by adding the "do-nothing" moves — the changes to \(x\) and \(y\) that keep \(ax + by\) the same:
Why that last step is exactly that. If you bump \(x\) up by \(b/d\) and \(y\) down by \(a/d\), the change in \(ax + by\) is \(a \cdot \frac{b}{d} - b \cdot \frac{a}{d} = 0\) — it cancels perfectly, so you land on another solution. And \(b/d\) is the smallest bump in \(x\) that can be undone by a whole-number change in \(y\), so stepping by \(k\) copies of it sweeps out every solution.
The classic mistake: forgetting to divide by \(d\)
Using step size \(b\) instead of \(b/d\) still gives valid solutions — but it skips some of them, so your "general solution" is incomplete. Always divide by the gcd.
Exam (May 2024, Problem 1): \(15x + 17y = 20\)
Solvable? \(\gcd(15, 17) = 1\), and \(1 \mid 20\), so yes.
One solution. From the worked example above, \(1 = 15 \cdot 8 + 17 \cdot (-7)\). Multiply through by \(20\) to hit the right-hand side:
so \((x_0, y_0) = (160, -140)\).
All solutions. Here \(d = 1\), so the steps are \(b/d = 17\) and \(a/d = 15\):
(Same set, just written with the pre-scaled \(8\) and \(-7\) and the factor of \(20\) visible.)
Exam (May 2023, Problem 2): non-negative solutions of \(23x + 31y = 1000\)
When a problem asks specifically for non-negative solutions, do the usual thing to get the full family, then bound \(k\). Impose \(x \geq 0\) and \(y \geq 0\) on the general solution; each gives an inequality on \(k\), and their overlap is a finite range of \(k\) values. Enumerate that range — the final answer is a short explicit list of pairs, not an infinite family. (The setup is the same recipe; the only new skill is turning two inequalities into a range and listing it.)
Modular arithmetic¶
Modular arithmetic is "clock arithmetic": we only care about remainders. We write \(a \equiv b \pmod n\) ("\(a\) is congruent to \(b\) mod \(n\)") to mean \(n \mid (a - b)\) — that \(a\) and \(b\) leave the same remainder on division by \(n\).
This is one of those equivalence relations from the previous chapter: it sorts the integers into \(n\) buckets by remainder, and those buckets are the elements of \(\mathbb{Z}_n\). Everything you do "mod \(n\)" is really arithmetic on the buckets.
Inverses¶
In ordinary arithmetic, dividing by \(a\) means multiplying by \(1/a\). Mod \(n\) there are no fractions, so "dividing by \(a\)" means multiplying by an inverse — a number \(a^{-1}\) with \(a \cdot a^{-1} \equiv 1 \pmod n\). Not every \(a\) has one:
When does an inverse exist?
\(a\) has an inverse mod \(n\) if and only if \(\gcd(a, n) = 1\) (they share no common factor).
How to find it. Solve \(ax + ny = 1\) with the extended Euclidean algorithm (possible exactly because \(\gcd(a,n) = 1\)). Then \(ax = 1 - ny \equiv 1 \pmod n\), so \(x\) is the inverse. The elements that have inverses form a group under multiplication, written \(\mathbb{Z}_n^{\times}\).
A shortcut worth spotting: \((n-1)^{-1} \bmod n\)
Notice \(n - 1 \equiv -1 \pmod n\). So \((n-1)^2 \equiv (-1)^2 = 1\). An element whose square is \(1\) is its own inverse, so \((n-1)^{-1} = n - 1\) with no algorithm needed. For instance \(89^{-1} \equiv 89 \pmod{90}\).
Keep an eye out for "squares to \(1\)" — it collapses an inverse computation to nothing, and it comes up in RSA problems all the time.
Solving linear congruences¶
\(ax \equiv b \pmod n\) is the modular cousin of \(ax = b\). How it behaves depends entirely on \(d = \gcd(a, n)\):
| Case | What happens | Why |
|---|---|---|
| \(d \nmid b\) | No solutions | \(ax\) is always a multiple of \(d\); if \(b\) isn't, you can't match it |
| \(d = 1\) | Exactly one solution: \(x \equiv a^{-1} b\) | \(a\) is invertible, so just multiply both sides by \(a^{-1}\) |
| \(d \mid b\), \(d > 1\) | \(d\) solutions mod \(n\) | divide the whole congruence by \(d\) and solve mod \(n/d\) |
The three-part drill \(6x \equiv 4 \pmod 7\), \(3x \equiv 4 \pmod 8\), \(6x \equiv 4 \pmod 9\) is built to march you through all three cases in a row — work out which case each one is before solving.
Fermat's little theorem¶
Fermat's little theorem
If \(p\) is prime and \(p \nmid a\), then
What it's for. It tames huge exponents. Since \(a^{p-1} \equiv 1\), powers of \(a\) cycle with period dividing \(p - 1\) — so to compute \(a^{k} \bmod p\) you can first reduce the exponent \(k\) modulo \(p - 1\). A giant exponent becomes a small one. (This is also the engine that makes RSA decryption work, below.)
Fast modular exponentiation¶
To compute something like \(a^k \bmod n\) by hand without the numbers exploding, use repeated squaring and reduce at every step:
- Write the exponent \(k\) in binary (as a sum of powers of two).
- Build up \(a^{2}, a^{4}, a^{8}, \dots\) by squaring the previous one, reducing mod \(n\) each time so the numbers stay small.
- Multiply together the pieces you need.
Worked slowly: \(2^{11} \bmod 35\)
Step 1 — exponent in binary. \(11 = 8 + 2 + 1\), so \(2^{11} = 2^{8} \cdot 2^{2} \cdot 2^{1}\).
Step 2 — build the powers, reducing as we go:
Step 3 — multiply the needed pieces (\(2^8 \equiv 11\), \(2^2 = 4\), \(2^1 = 2\)):
The golden rule: reduce mod \(n\) before you multiply on, never after — that's what keeps every intermediate number under \(n^2\) and the arithmetic doable by hand. (Sanity check: \(2^{10} = 1024 \equiv 9 \pmod{35}\), and \(9 \cdot 2 = 18\). ✓)
The RSA cryptosystem¶
Strip away the security story and RSA is just Fermat's little theorem turned into a protocol. Every exam poses essentially the same four-part question, so learn the moves once.
The setup in one breath: two people want to send secret messages. The recipient publishes a "lock" everyone can use (\(n\) and \(e\)) but keeps the "key" secret (\(d\)). Anyone can encrypt; only the holder of \(d\) can decrypt.
Key generation¶
- Choose two distinct primes \(p\) and \(q\).
- Compute \(n = pq\) and \(m = (p-1)(q-1)\).
- Choose an encryption key \(e\) with \(\gcd(e, m) = 1\) (so \(e\) has an inverse mod \(m\)).
- Compute the decryption key \(d\) as that inverse: \(ed \equiv 1 \pmod m\).
The public key is the pair \((n, e)\) — safe to shout from the rooftops. The private key is \(d\). Crucially, \(p\), \(q\), and \(m\) must stay secret: anyone who learns \(m\) can compute \(d\) immediately and read everything.
Encryption and decryption¶
The moduli are different — this is the #1 mistake
Messages are raised to powers mod \(n\), but the keys \(e, d\) are inverses mod \(m\). Two different moduli in one problem. Whenever you compute \(d\), you're working mod \(m\); whenever you encrypt or decrypt, you're working mod \(n\). Keep them straight.
Exam (May 2024, Problem 3): RSA with \(p = 5\), \(q = 7\)
First, the parameters: \(n = 5 \cdot 7 = 35\) and \(m = (5-1)(7-1) = 4 \cdot 6 = 24\).
(a) What condition must \(e\) satisfy, and what's the smallest valid \(e\) in \(10 \le e \le 15\)? The condition is \(\gcd(e, m) = \gcd(e, 24) = 1\). Test the range: \(10, 12, 14\) are even (share factor \(2\) with \(24\)); \(15\) shares factor \(3\). The one left is \(e = 11\). ✓
(b) Find the decryption key \(d\). We need \(11d \equiv 1 \pmod{24}\). Try the squares-to-\(1\) shortcut: \(11^2 = 121 = 5 \cdot 24 + 1 \equiv 1 \pmod{24}\). So \(11\) is its own inverse and \(d = 11\).
(c) Encrypt \(a = 2\). Compute \(2^{e} = 2^{11} \bmod 35\). Using \(2^8 \equiv 11\) from the exponentiation example:
The encrypted message is \(18\).
(d) How do you decrypt? Recover the message as \(x \equiv y^{d} \bmod 35\) — you're asked to state the formula, not grind it out.
The published solution has a typo here
The official solution writes this as \(2^{13} = 2^8 \cdot 2^4 \cdot 2 \equiv 11 \cdot 4 \cdot 2 \equiv 18\). Two things are mislabelled: the exponent should be \(11\) (the \(e\) from part (a)), not \(13\), and \(2^4 = 16\), not \(4\). The factors \(11 \cdot 4 \cdot 2\) are really \(2^8 \cdot 2^2 \cdot 2^1 = 2^{11}\), so the final answer \(18\) is correct — only the labels are wrong. (For the record, \(2^{13} \equiv 2 \pmod{35}\).)
The takeaway: solution sheets are not gospel. If your arithmetic disagrees with one, recheck it before assuming you're the one who's wrong.
Why decryption actually recovers the message
Decrypting computes \(y^d \equiv (x^e)^d = x^{ed} \pmod n\). Since \(ed \equiv 1 \pmod m\), we have \(ed = 1 + km\) for some \(k\), so \(x^{ed} = x \cdot (x^{m})^{k}\). Fermat's little theorem (applied to the primes \(p\) and \(q\) separately) gives \(x^{m} \equiv 1\), which collapses the tail and leaves just \(x\). If you can reconstruct this chain, you'll never forget which modulus is which — because it's Fermat's theorem that forces \(m = (p-1)(q-1)\) to be the exponent's modulus.