Saturday, 18 May 2013

The Euclidean Algorithm and the Extended Euclidean Algorithm

This is the last trick needed to understand the RSA method. The first algorithm is a quick(-ish) method to find the greatest common divisor between two numbers (a and b). The second algorithm also calculates values of x and y that satisfies the following equation:
$ax + by = gcd(a,b)$

The Euclidean Algorithm:

This is best explained using an example. What is the greatest common divisor between 120 and 16?
1. First calculate 120 mod 16 = 8.
2. Then replace 120 with 16, and 16 with the remainder of the last step, 8. 16 mod 8 = 0
3. The result of zero signals the end of the algorithm, and the last divisor (8) is the greatest common divisor of 120 and 16.
Here's a second example, gcd(150,23):
1. 150 mod 23 = 12
2. 23 mod 12 = 11
3. 12 mod 11 = 1
4. 11 mod 1 = 0
So the greatest common divisor is 1. In short, 150 and 23 are coprime to one another.

The Extended Euclidean Algorithm:

The Extended Euclidean Algorithm is, as its name suggests, an extension to this algorithm.
Each stage in the Euclidean Algorithm can be written as an iterative equation:
$r_i = ax_i + by_i$
and the remainders as:
$r_i = r_{i-2} – q_i \cdot r_i$
Or, in words, the remainder value two steps ago (120 on the first example) minus the last quotient (7) times the value one step ago (16).
$r_2 = 120 – 7 \cdot 16$
$r_2 = 8$.
Substituting:
$r_i = (ax_{i-2} + by_{i-2}) – q_{i – 1} \cdot (ax_{i – 1} + by_{i – 1} )$
Our initial values are:
$r_1 = a = a \times 1 + b \times 0$
$r_2 = b = b \times 0 + b \times 1$

$x_1 = 1, y_1 = 0$
$x_2 = 0, y_2 = 1$
And (using the formula for the remainders):
$x_i = x_{i– 2} – q_{i – 1} \cdot x_{i– 1 }$
$y_i = x_{i– 2} – q_{i – 1} \cdot y_{i – 1}$

q r x y

120 1 0

16 0 1
7 (120*1 + 16*0) – 7*(120*0 + 16*1)
=8
1 – 7*0
= 1
0 – 7*1
= -7
2 (120*0 + 16*1) – 2 *(120*1 + 16* -7)
= 0

Taking the second last set of values, 120 * 1 + 16* – 7 = 8.