GCD, modular arithmetic & the Euclidean algorithm

The setting: arithmetic on integers measured in bits

Number-theoretic algorithms operate on integers, but we measure their cost by the number of bits in the input, not by the value. If $n$ is a $\beta$-bit number then $\beta = \lceil \lg n \rceil$, and an algorithm is *polynomial-time* only if it runs in time polynomial in $\beta$. This is why testing every divisor up to $\sqrt{n}$ is not polynomial — there are about $2^{\beta/2}$ of them — while the Euclidean algorithm, which runs in $O(\beta)$ arithmetic operations, *is*.

Divisibility, gcd, and the recursion theorem

We write $d \mid a$ ("$d$ divides $a$") when $a = kd$ for some integer $k$. The greatest common divisor $\gcd(a,b)$ is the largest integer dividing both $a$ and $b$. Two integers are relatively prime when $\gcd(a,b)=1$.

The whole algorithm rests on one fact, the GCD recursion theorem:

$$\gcd(a,b) = \gcd(b,\; a \bmod b)\quad\text{for } b > 0.$$

Why it holds: any common divisor of $a$ and $b$ also divides $a \bmod b = a - \lfloor a/b \rfloor b$ (a linear combination of $a$ and $b$), and conversely. So the two pairs share *exactly* the same set of common divisors, hence the same greatest one.

Euclid's algorithm

Apply the recursion until the second argument is $0$, then return the first (since $\gcd(a,0)=a$):

$$\text{EUCLID}(a,b):\quad \textbf{if } b=0 \textbf{ then return } a; \textbf{ else return } \text{EUCLID}(b,\, a \bmod b).$$

Worked example — $\gcd(252,105)$. Each line applies $\gcd(a,b)=\gcd(b,a\bmod b)$:

- $\gcd(252,105)$: $252 = 2\cdot105 + 42$, so $\to \gcd(105,42)$ - $\gcd(105,42)$: $105 = 2\cdot42 + 21$, so $\to \gcd(42,21)$ - $\gcd(42,21)$: $42 = 2\cdot21 + 0$, so $\to \gcd(21,0)$ - $\gcd(21,0) = 21$. ✓

Running time (Lamé's theorem). The worst case for a given number of steps is *consecutive Fibonacci numbers*: $\text{EUCLID}(F_{k+1},F_k)$ makes the most recursive calls of any pair with $b \le F_k$. Because $F_k \approx \varphi^k/\sqrt5$ grows exponentially, the number of calls is $O(\log_\varphi b) = O(\lg b) = O(\beta)$. So Euclid is $O(\beta)$ arithmetic operations — logarithmic in the value, linear in the bit length.

Extended Euclid and modular inverses

$\text{EXTENDED-EUCLID}(a,b)$ returns a triple $(d,x,y)$ where $d = \gcd(a,b) = ax + by$ — the Bézout coefficients. The recursion carries the coefficients back up: if the recursive call on $(b,\,a\bmod b)$ returns $(d,x',y')$, then

$$d = bx' + (a\bmod b)y' = bx' + (a - \lfloor a/b\rfloor b)y' = a\,y' + b\big(x' - \lfloor a/b\rfloor y'\big),$$

so we return $(d,\; y',\; x' - \lfloor a/b\rfloor y')$. This is the engine for modular inverses: $a^{-1} \bmod n$ exists iff $\gcd(a,n)=1$, and then it is $x \bmod n$ from $\text{EXTENDED-EUCLID}(a,n)$. (Take the positive representative: $x$ may come back negative.) Modular inverses are exactly what RSA key generation needs in lesson 8.2.

Modular exponentiation by repeated squaring

RSA encrypts with $a^b \bmod n$ for *huge* $b$, so we can never multiply $b$ times. Instead use the binary expansion of the exponent: scanning the bits of $b$, square the running value for every bit and multiply in $a$ for every $1$-bit. That is $O(\lg b) = O(\beta)$ modular multiplications:

$$a^{13} = a^{1101_2} = ((a^2\cdot a)^2)^2 \cdot a.$$

Reducing $\bmod\, n$ after every step keeps every intermediate value below $n^2$, so the numbers never blow up. With $O(\beta)$ multiplications, each $O(\beta^2)$ bit operations, the total is $O(\beta^3)$ bit operations — the cost of one RSA decryption.