This algorithm not only finds the gcd of two integers it also finds the modular inverses (a.k.a. multiplicative inverse) of those numbers. If gcd(a, b)=1, then we know there exists a-1(mod b) and b-1(mod a). In other words a-1*a≡1(mod b), or a-1*a mod b=1.

Finding a multiplicative inverse is very important in some cryptographic systems. Like the Hill Cipher.

Extended Euclidean algorithm is really the same as the Euclidean Algorithm except instead of using mod we use division to find the quotient and calculate the remainder. This and a few side calculations allow us to not only find the greatest common divisor of a and b, but also their modular inverses. Extended Euclidean algorithm uses the equation a*u + b*v=1. This will only be true when u is the modular inverse of a(mod b) and v is the modular inverse of b(mod a). But it is not always true that we can find these modular inverses they only exist when gcd(a,b) is equal to 1. But even when they don't exist we can still use the algorithm to find the gcd, because that 1 is really the just a remainder. So the equation we rely on is really a*u + b*v = r.

Finding the quotient, q, instead of just the remainder allows us to use the quotient to caluculate auxillary numbers u and v. Where ui = ui-2 - ui-1*qi-2 (mod a) and vi = vi-2 - vi-1*qi-2 (mod b). Now you just run through normal Euclid's Algorithm finding the remainder, ri, using the quotient, qi=int(ai/bi), instead of ai mod bi. Starting with i=0. But since u and v are calculated from previous values we can't caluculate them until i=2. So when a < b for i=0, we set u0=0 and v0=1, for i=1, we set u1=1 and v1=0. We pick these numbers so that for i=0, r = a, and for i=1, r = b, using the a*u + b*v = r equation. Reverse this for a > b.

For some this may be easier to understand given psuedocode. Here is some that performs the Extend Euclidian Algorithm, egcd(a, b). (u, v, r) and (U, V, R) are used to keep the calculations of past values and makes the algorithm more memory effient than the hand written method because you don't need to keep so much history of the auxillary numbers.

Step 1:
if a < b then
Set u=0, v=1, and r=b
Set U=1, V=0, and R=a
else
Set u=1, v=0, and r=a
Set U=0, V=1, and R=b
Step 2:
if R = 0 then return r (for the gcd) and no inverses exist.
if R = 1 then return R (for the gcd), V (for the inverse a(mod b)) and U (for the inverse of b(mod a)).
Step 3:
Calculate q = int(r/R)
Calculate t1 = u - U*q
Calculate t2 = v - V*q
Calculate t3 = r - R*q
set u=U, v=V, r=R
set U=t1, V=t2, R=t3
goto Step 2.

Note: throughout the algorithm the following relationships hold
b*t1 + a*t2 = t3
b*u + a*v = r
b*U + a*V = R
You can also combine this algorithm with the binary method to increase its efficiency, called the Extended Binary Euclidean Algorithm. (I would node that, but I haven't been able to figure out how the implementation I've seen works) Suggested reading: Euclid's Algorithm, greatest common divisor, and Binary GCD algorithm.

Here is a java implementation:

    public int[] extEuclid(int a, int b) {
        if (b == 0) {
            int result[] = {1, 0, a};
            return result;
        }

        int u = a;
        int v = b;
        int x1, x2, x3, y1, y2, y3;

        if (u < v) {
            x1 = 0; x2 = 1; x3 = v;
            y1 = 1; y2 = 0; y3 = u;
        } else {
            x1 = 1; x2 = 0; x3 = u;
            y1 = 0; y2 = 1; y3 = v;
        }

        while (y3 > 1) {
            int q = (int) (x3/y3);
            int t1 = x1 - q*y1;
            int t2 = x2 - q*y2;
            int t3 = x3 - q*y3;

            x1 = y1; x2 = y2; x3 = y3;
            y1 = t1; y2 = t2; y3 = t3;
        }
        if (y3 == 0) {
            int result[] = {x1, x2, x3};
            return result;
        } else {
            int result[] = {y1, y2, y3};
            return result;
        }
    }

There is a quick and easy way to work out the Extended Euclidean Algorithm with pen and paper.

It involving creating a grid like this:

--+--+--+--+--+--+- ... -+----
Q:| 1| 0|QO|Q1|Q2|  ...  |
--+--+--+--+--+--+- ... -+----
P:| 0| 1|P0|P1|P2|  ...  |
--+--+--+--+--+--+- ... -+----
q:|  |  |qo|q1|q2|  ...  |qn|
--+--+--+--+--+--+- ... -+----
r:|  | a| b|r0|r1|  ...  |rn|
--+--+--+--+--+--+- ... -+----
r:|  |r0|r1|r2|r3|  ... 
--+--+--+--+--+--+- ... -+----

Where a and b correspond to a and b on Xamot's wu, ri is the remainder of ri-2/ri-1 (consider a and b r-2 and r-1), and qi the quotient of the same division.

Now the Q and P rows correspond roughly to the x's and y's in Xamot's wu. The calculation for them is as follows:

Pi=qi*Pi-1+Pi-2
Qi=qi*Qi-1+Qi-2

The way to proceed is as follows, we usually perform the simple Euclid's Algorithm first:

--+--+--+--+--+--+--+
q:|  |  | 1| 1| 2|  |
--+--+--+--+--+--+--+
r:|  |12| 7| 5| 2| 1|
--+--+--+--+--+--+--+
r:|  | 5| 2| 1|  |  |
--+--+--+--+--+--+--+

Then we proceed with Qi's and Pi's

--+--+--+--+--+--+--+
Q | 1| 0| 1| 1| 3|
--+--+--+--+--+--+--+
P | 0| 1| 1| 2| 5|
--+--+--+--+--+--+--+
q:|  |  | 1| 1| 2|  |
--+--+--+--+--+--+--+
r:|  |12| 7| 5| 2| 1|
--+--+--+--+--+--+--+
r:|  | 5| 2| 1|  |  |
--+--+--+--+--+--+--+

So the final Q's and P's are 3 and 5, yielding the Bezout's Identity:

3*12+(-5)*7=1 (signs for Qi and Pi alternate, one is positive for even i's and negative for odd; and the other is the opposite)

Notice that calculating Pi and Qi is really quick, it involves looking up their previous values and qi just below.

As usual, furher help is granted by msg'ing me ;-)

Log in or register to write something here or to contact authors.