Arnab Chakraborty's cryptography tutorial: page 7 of 11

cwave.eu5.org
Also see: http://www.angelfire.com/dragon/letstry
cwave04 at yahoo dot com

My Guestbook

Last updated on Fri May 21 11:50:25 IST 2010.

Home >

... tutorials >

... ... Cryptography

The extended Euclidian algorithm

It is based on the same idea as the simple Euclidian algorithm: to find gcd of a and b divide a by b to get remainder r, and then compute the gcd of b and r. This works because of the identity:

gcd(a,b) = gcd(b,r),

where r is the remainder of a upon division by b.

Now suppose that you can find m₁ and n₁ such that

gcd(b,r) = m₁ b + n₁ r.

If a = b q + r, then you can easily obtain m and n (in terms of m₁, n₁ and q) such that

gcd(a,b) = m a + n b.

To use this in a C program we can use recursion. Let us write a C function that computes gcd(a,b) and m, n as in (*).


void gcd(a, b, &g, &m, &n) {

  int q, r, m1, n1, g1;

  
  /*Compute q and r*/

  /* If r is zero, then b | a. So b = 0a + 1b is the gcd.
  if(r==0) {
    *g = b;
    *m = 0;
    *n = 1;
    return;
  }
    
  gcd(b, r, &g1, &m1, &n1);
  
  *g = g1;

  /*Compute m, n from q, m1 and n1:

    *m = ... ;
    *n = ... ;

   */
}