Sunny Ahuwanya's Blog

Mostly notes on .NET and C#

The Extended Euclidean Algorithm

In cryptographic systems, it is usually necessary to calculate the inverse of the modulus function of one number to another.

For example xy = 1 mod 317. As expected it can be very difficult to compute x for any given y.

The Extended Euclidean Algorithm provides an elegant way to calculate this inverse function. The Algorithm calculates the greatest common divisor (gcd) of  two integers.

y, the inverse of x exists if and only if gcd(x, n) = 1

i.e. , for an integer s, there exists an integer y such that xy + sn = 1, where y is the inverse of x mod n, also known as the modular inverse.

To calculate y, using the Extended Euclidean function:
 

The Extended Euclidean Algorithm for finding the inverse of a number mod n.

We will number the steps of the Euclidean algorithm starting with step 0. The quotient obtained at step i will be denoted by qi. As we carry out each step of the Euclidean algorithm, we will also calculate an auxillary number, yi. For the first two steps, the value of this number is given: y0 = 0 and y1 = 1. For the remainder of the steps, we recursively calculate yi = yi-2 - yi-1 qi-2 (mod n). Continue this calculation for one step beyond the last step of the Euclidean algorithm.

The algorithm starts by "dividing" n by x. If the last non-zero remainder occurs at step k, then if this remainder is 1, x has an inverse and it is yk+2. (If the remainder is not 1, then x does not have an inverse.) Here is an example:

Find the inverse of 15 mod 26.

Step 0:             26 = 1(15) + 11           y0 = 0

Step 1:             15 = 1(11) + 4             y1 = 1

Step 2:             11 = 2(4) + 3   y2 = 0 - 1( 1) mod 26 = 25

Step 3:             4 = 1(3) + 1     y3 = 1 - 25( 1) mod 26 = -24 mod 26 = 2

Step 4:             3 = 3(1) + 0     y4 = 25 - 2( 2) mod 26 = 21

                        y5 = 2 - 21( 1) mod 26 = -19 mod 26 = 7


Notice that 15(7) = 105 = 1 + 4(26) is equivalent to 1 (mod 26).

The Extended Euclidean Algorithm is a gift, cryptographically speaking, even though it has many more applications beyond cryptography.

References:
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm http://www.antilles.k12.vi.us/math/cryptotut/extended_euclidean_algorithm.htm