Euclid's Algorithm

Euclid's Algorithm

1. GCD and Why Crypto Needs It

$\gcd(a, b)$ = largest $d$ dividing both. Crypto uses it to test invertibility ($a^{-1} \bmod n$ exists ⟺ $\gcd(a,n) = 1$), to compute the inverse itself, and inside RSA key generation ($\gcd(e, \phi(n)) = 1$), primality helpers, and polynomial fields.

Worked intuition: $\gcd(48, 18)$: divisors of 48: $1,2,3,4,6,8,12,16,24,48$; of 18: $1,2,3,6,9,18$ → common max $6$.

2. Basic Euclid (Worked)

Theorem: $\gcd(a, b) = \gcd(b, a \bmod b)$. Repeatedly replace until remainder $0$:

gcd(252, 198):
252 = 1×198 + 54  → gcd(198, 54)
198 = 3×54 + 36   → gcd(54, 36)
54  = 1×36 + 18   → gcd(36, 18)
36  = 2×18 + 0    → gcd = 18 ✓

Only $4$ divisions for 3-digit numbers — complexity $O(\log \min(a,b))$ (Lamé: steps $\le 5 \times$ digits). Second trace (exam-size): $\gcd(1970, 1066)$: $1970 = 1 \times 1066 + 904$; $1066 = 1 \times 904 + 162$; $904 = 5 \times 162 + 94$; $162 = 1 \times 94 + 68$; $94 = 1 \times 68 + 26$; $68 = 2 \times 26 + 16$; $26 = 1 \times 16 + 10$; $16 = 1 \times 10 + 6$; $10 = 1 \times 6 + 4$; $6 = 1 \times 4 + 2$; $4 = 2 \times 2 + 0$ → $\gcd = 2$.

3. Extended Euclid: Bézout + Inverses (The Money Section)

Extended Euclid finds $x, y$ with Bézout identity:

If $\gcd(a, n) = 1$: $ax + ny = 1 \Rightarrow ax \equiv 1 \pmod n$ → $x \bmod n = a^{-1}$.

Worked inverse: $7^{-1} \bmod 40$ (RSA-style: $e = 7$, $\phi = 40$). Euclid: $40 = 5 \times 7 + 5$; $7 = 1 \times 5 + 2$; $5 = 2 \times 2 + 1$; $2 = 2 \times 1 + 0$. Back-substitute: $1 = 5 - 2 \times 2$; $2 = 7 - 1 \times 5$ → $1 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7$; $5 = 40 - 5 \times 7$ → $1 = 3(40 - 5 \times 7) - 2 \times 7 = 3 \times 40 - 17 \times 7$. So $x = -17 \equiv 23 \pmod{40}$: $7^{-1} = 23$. Check: $7 \times 23 = 161 = 4 \times 40 + 1$ ✓.

Tabular shortcut (fewer errors): track $(r, x)$ rows: $(40, 0)$, $(7, 1)$; quotient $q = 5$ → row $(5, 0 - 5 \times 1 = -5)$; $q = 1$ → $(2, 1 - 1(-5) = 6)$; $q = 2$ → $(1, -5 - 2 \times 6 = -17)$ → inverse $-17 \equiv 23$ ✓. Same answer, mechanical.

4. Uses and Pitfalls

• RSA: $d = e^{-1} \bmod \phi(n)$ exactly as above; $\gcd(e, \phi) = 1$ check first — if $
  e 1$, pick new$e$.
• Polynomial version (same algorithm, degree replaces size) gives AES $GF(2^8)$ inverses (Topic 4).
• Binary/GCDвлека: never "divide" mod $n$ without $\gcd = 1$; negative $x$ always reduced $+n$; Euclid on $(0, n)$ returns $n$.

Exam Points

• Remainder-chain trace ($\gcd(252,198) = 18$) — 2–3 mark opener.
• Extended back-substitution to $7^{-1} = 23 \bmod 40$ with check $7 \times 23 = 161 \equiv 1$ — favourite 5-marker.
• Bézout statement + "inverse ⟺ gcd 1" condition.
• Table method as safe alternative; RSA $d$ link.