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\mathrm{mod}b)\text{for }b>0.$$

Why it holds: any common divisor of $a$ and $b$ also divides $a\mathrm{mod}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):\text{if }b=0\text{ then return }a;\text{ else return }\text{EUCLID}(b,a\mathrm{mod}b).$$

Worked example — $\gcd (252,105)$. Each line applies $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$:

• $\gcd (252,105)$: $252=2\cdot 105+42$, so $\to \gcd (105,42)$
• $\gcd (105,42)$: $105=2\cdot 42+21$, so $\to \gcd (42,21)$
• $\gcd (42,21)$: $42=2\cdot 21+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 {\phi }^k/\sqrt{5}$ grows exponentially, the number of calls is $O({\log }_{\phi }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\mathrm{mod}b)$ returns $(d,x^{\prime },y^{\prime })$, then

$$d=b{x}^{\prime }+(a\mathrm{mod}b)y^{\prime }=b{x}^{\prime }+(a-\lfloor a/b\rfloor b)y^{\prime }=a{y}^{\prime }+b(x^{\prime }-\lfloor a/b\rfloor y^{\prime }),$$

so we return $(d,y^{\prime },x^{\prime }-\lfloor a/b\rfloor y^{\prime })$. This is the engine for modular inverses: $a^{-1}\mathrm{mod}n$ exists iff $\gcd (a,n)=1$, and then it is $x\mathrm{mod}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\mathrm{mod}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 $\mathrm{mod}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.