egcd.c:

/* Extended GCD */
/* Given x, y, find a,b,v such that ax+by=gcd(x,y) */

void egcd (x,y,ao,bo,vo) long x,y,*ao,*bo,*vo; {
  long temp;
  long A,B,C,D,u,v,g;

  if (x<0) { x = -x; } 
  if (y<0) { y = -y; }
  if (x<y) { temp = x; x = y; y = temp;}

  g = 0;
  while ((0 == (x & 1)) && (0 == (y & 1))) { /* While both even */ 
    x >>= 1; y >>= 1; g++;
  }

  u = x; v = y; A=1; B=0; C=0; D=1;

  while (u != 0) {

     while (0 == (u&1)) { 
       u >>= 1;
       if ((0!=(A&1))||(0!=(B&1))) {
          A += y; B -= x;
       }
       A >>= 1; B >>= 1;
     }

     while (0 == (v&1)) {
       v >>= 1;
       if ((0!=(C&1)) || (0!=(D&1))) {
          C += y; D -= x;
       }
       C >>= 1; D >>= 1;
     }

     if (u>=v) {
        u -= v; A -= C; B -= D;
     } else {
        v -= u; C -= A; D -= B;
     }

  }
  *ao=C; *bo=D; *vo=v<<g;
}

Go to ...

• Factoring Page
• John Halleck's Home Page

This page is http://www.cc.utah.edu/~nahaj/factoring/egcd.c.html
© Copyright 2003 by John Halleck, All Rights Reserved.
This snapshot was last modified on January 12th, 2009
And the underlying file was last modified on December 12th, 2005