Monday, July 13, 2009

Extended Euclidean Algorithm


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 ri = axi + byi 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:

r1 = a = a(1) + b(0)
r2 = 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...

The computation proceeds as follows:
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.
Algorithm:
By routine algebra of expanding and grouping like terms (refer to the previous example), the following algorithm for iterative method is obtained:
  1. Apply Euclidean algorithm, and let qn(n starts from 1) be a finite list of quotients in the division.
  2. Initialize x0, x1 as 1, 0, and y0, y1 as 0,1 respectively.
  3. Then for each i so long as qi is defined,
    • Compute xi+1= xi-1- qixi
    • Compute yi+1= yi-1- qiyi
    • Repeat the above after incrementing i by 1.
  4. The answers are the second-to-last of xn and yn.
Sample Program:
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...

11 comments:

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

    ReplyDelete
  2. Thanks 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.

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

    ReplyDelete
  4. I 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

    ReplyDelete
  5. Thank 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
  6. -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
    Replies

    1. -9 * 120 = -1080

      23 | -1080 | -47
      | -1081 |
      ---------
      1

      As -1080 > -1081

      Delete
  7. Excellent Tutorial!! Thank you very much.

    ReplyDelete
  8. Now I got a rough picture of how this's going thank you but, mind if I ask how you got

    "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.

    ReplyDelete
  9. Thanks 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