Euclid's Algorithm

Greatest Common Divisor

The Euclid's algorithm finds the greatest common divisor between 2 (or more) positive integers. For instance, finding the GCD of 4674 and 343 is as follows:

GCD(4676, 343)
GCD(343, 4676 mod 343)
GCD(217, 343 mod 217)
GCD(126, 217 mod 126)
GCD(91, 126 mod 91)
GCD(35, 91 mod 35)
GCD(21, 35 mod 21)
GCD(14, 21 mod 14)
GCD(7, 14 mod 7)
GCD(7, 0)

Because we eventually end with a remainder of 0, we then know that 7 is the highest common divisor for 4676 and 343. If we end with a remainder of 1 then the 2 numbers are relatively prime.

Extended Euclid's Algorithm

The multiplicative inverse can be found by using the extended Euclid's algorithm, which is essentially when the GCD(X, Y) = 1 then X has a multiplicative inverse modulo Y, where X < Y and X^-1 < Y, such that X * X^-1 ≡ 1 mod Y.

Set up a table that uses the following equations:

Qi+1 = int(Ri-1 / Ri)
Ri+1 = Ri-1 mod Ri
Ui+1 = Ui-1 - (Qi+1 * Ui)
Vi+1 = Vi-1 - (Qi+1 * Vi)

For example we want to find the multiplicative inverse to 28 * 28^-1 ≡ 1 mod 75:

Q R U  V
----------------------
- 75 0 1 Initial set up
- 28 1 0 Initial set up
----------------------
2 19 -2 1 Begin calculations
1 9 3 -1
2 1 -8 3

Once you get a 1 under R then you have found the multiplicative inverse under U. In this case the multiplicative inverse for 28 * 28^-1 ≡ mod 75, is -8, which also equals 67 (in mod 75). Aside from calculating the product mod 75, to check this you can also do the following:

Since we know that the GCD(75, 28) = 1
We have 1 = U * 28 + V * 75
1 = -8 * 28 + 3 * 75
1 = -224 + 225, checks!

The extended Euclidean algorithm is extensively used in public key cryptosystems for instance, in RSA and ElGamal.

Links

http://www.cut-the-knot.com/blue/Euclid.shtml
http://users.erols.com/eweidaw/applets/EuclidExtension.html
http://mathforum.org/epigone/math-learn/whehvalzee
http://www.nist.gov/dads/HTML/euclidalgo.html
http://www.nist.gov/dads/HTML/extendEuclid.html
http://ce.sharif.edu/~ghodsi/ds-alg-dic/HTML/extendEuclid.html