**Extended Euclidean Algorithm**is an extension of standard Euclidean Algorithm for finding the GCD of two integers a and b. It also calculates the values of two more integers x and y such that:

**ax + by = gcd(a,b)**; where typically either x or y is negative. This algorithm is generally used to find multiplicative inverse in a finite field, because, if ax + by = gcd(a,b) = 1, i.e. a and be are co-primes, then x is the modular multiplicative inverse of a modulo b, and similarly, y is the modular multiplicative inverse of b modulo a.

This method computes expressions of the form *r*_{i} = *a**x*_{i} + *b**y*_{i} for the remainder in each step *i* of the Euclidean algorithm. Each modulus can be written in terms of the previous two remainders and their whole quotient as follows:

By substitution, this gives:

The first two values are the initial arguments to the algorithm:

*r*_{1}=*a*=*a*(1) +*b*(0)*r*_{2}=*b*=*a*(0) +*b*(1)

The expression for the last non-zero remainder gives the desired results since this method computes every remainder in terms of *a* and *b*, as desired.

**Example:** Compute the GCD of 120 and 23. Or, more formally, compute: x, y, g for 120x + 23y = g; where x, y are two integers and g is the gcd of 120 and 23...

- Initial values:
__Step 1:__Reminder = 120;

Combine terms: 120 = 120 x 1 + 23 x 0__Step 2:__Reminder = 23;

Combine terms: 23 = 120 x 0 + 23 x 1

Iterative steps:__Step 3:__Quotient = 120 / 23 = 5; Reminder = 120 % 23 = 5;

5 = 120 - 23 x 5

=> 5 = (120 x 1 + 23 x 0) - (120 x 0 + 23 x 1) x 5 ;[from Step 1 and 2]

=> 5 = 120 x 1 + 23 x -5__Step 4:__Quotient = 23 / 5 = 4; Reminder = 23 % 5 = 3;

3 = 23 - 5 x 4

=> 3 = (120 x 0 + 23 x 1) - (120 x 1 + 23 x -5) x 4 ;[from Step 2 and 3]

=> 3 = 120 x -4 + 23 x 21__Step 5:__Quotient = 5 / 3 = 1; Reminder = 5 % 3 = 2;

2 = 5 - 3 x 1

=> 2 = (120 x 1 + 23 x -5) - (120 x -4 + 23 x 21) x 1 ;[from Step 3 and 4]

=> 2 = 120 x 5 + 23 x -26__Step 6:__Quotient = 3 / 2 = 1; Reminder = 3 % 2 = 1;

1 = 3 - 2 x 1

=> 1 = (120 x -4 + 23 x 21) - (120 x 5 + 23 x -26) x 1 ;[from Step 4 and 5]

=> 1 = 120 x -9 + 23 x 47

End of Algorithm.

The last line reads 1 = −9×120 + 47×23, which is the required solution: *x* = −9 and *y* = 47, and obviously g = gcd(120,23) = 1

This also means that −9 is the multiplicative inverse of 120 modulo 23, and that 47 is the multiplicative inverse of 23 modulo 120.

- −9 × 120 ≡ 1
**mod**23 and also 47 × 23 ≡ 1**mod**120.

By routine algebra of expanding and grouping like terms (refer to the previous example), the following algorithm for iterative method is obtained:

- Apply Euclidean algorithm, and let q
_{n}(n starts from 1) be a finite list of quotients in the division. - Initialize x
_{0}, x_{1}as 1, 0, and y_{0}, y_{1}as 0,1 respectively. - Then for each i so long as q
_{i}is defined, - Compute x
_{i+1}= x_{i-1}- q_{i}x_{i} - Compute y
_{i+1}= y_{i-1}- q_{i}y_{i} - Repeat the above after incrementing i by 1.
- The answers are the second-to-last of x
_{n}and y_{n}.

Here is a sample program written in C++ which implements the Extended Euclidean Algorithm:

#include <stdio.h>

/*

Takes a, b as input.

Returns gcd(a, b).

Updates x, y via pointer reference.

*/

int Extended_Euclid(int A, int B, int *X, int *Y)

{

int x, y, u, v, m, n, a, b, q, r;

/* B = A(0) + B(1) */

x = 0; y = 1;

/* A = A(1) + B(0) */

u = 1; v = 0;

for (a = A, b = B; 0 != a; b = a, a = r, x = u, y = v, u = m, v = n)

{

/* b = aq + r and 0 <= r < a */

q = b / a;

r = b % a;

/* r = Ax + By - aq = Ax + By - (Au + Bv)q = A(x - uq) + B(y - vq) */

m = x - (u * q);

n = y - (v * q);

}

/* Ax + By = gcd(A, B) */

*X = x; *Y = y;

return b;

}

int main()

{

int a, b, x, y, g;

scanf("%d %d", &a, &b);

g = Extended_Euclid(a, b, &x, &y);

printf("X = %d; Y = %d; G = %d\n", x, y, g);

return 0;

}

Python implementation:

def Extended_Euclid(a, b):

x, last_x = 0, 1

y, last_y = 1, 0

while b:

quotient = a / b

a, b = b, a % b

x, last_x = last_x - quotient*x, x

y, last_y = last_y - quotient*y, y

return (last_x, last_y, a)

For complete reading, click here. It is also useful to have a look at the Chinese Remainder Theorem.

Hope this will help...

Excellent tutorial :-). Thanks a lot :-)

ReplyDeleteThanks for the comment, but you see, the actual credit goes to wikipedia, as this is just an adaptation from wikipedia, I also mentioned the respective links throughout the post.

ReplyDeleteThe Python implementation is the exact conversion of the algorithm from wikipedia. Looks like its a good idea to learn python. i hate temporary variables.

ReplyDeleteI got a huge crush on python when I wrote this, so whenever I came across a piece of code, I tried to convert that to python :p

ReplyDeleteThank you pretty much. Now I can use it to find inverse mod(actually before reading it I did not know how to find inverse mod)

ReplyDelete-9 * 120 (mod 23) =1 ........... i don't understand the process. Actually i am pretty much new in Modular Arithmetic. I will be very happy if you reply me on this easy calculation

ReplyDelete

Delete-9 * 120 = -1080

23 | -1080 | -47

| -1081 |

---------

1

As -1080 > -1081

Excellent Tutorial!! Thank you very much.

ReplyDeleteNow I got a rough picture of how this's going thank you but, mind if I ask how you got

ReplyDelete"3 = 120 x -4 + 23 x 21" from "3 = (120 x 0 + 23 x 1) - (120 x 1 + 23 x -5) x 4"? I am stuck here.

Good tutorial!

ReplyDeleteThanks for the examples! just a comment: when I run the Python version with Python 3.4.3 |Anaconda 2.3.0 (64-bit) version, I receive x,y as decimal numbers. Just changing the line quotient = a / b by quotient = int(a / b) will fix it.

ReplyDelete