CodeArchive ExtendedGCD

From Ubcacm
Revision as of 21:49, 29 January 2007 by 142.103.22.72 (Talk)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Extended GCD, Modular Inverse

Find a x + b y = d where d is (a,b).

int egcd(int a, int b, int& x, int &y) {
  if (!b) { x = 1; y = 0; return a; }
  int result = egcd(b, a%b, y, x);
  y -= x * (a/b);
  return result;
}

Canonical Extended GCD

Given a, b, c, >=0, find smallest x, y >=0 s.t. ax-by = c (if possible)

bool canon_egcd(int a, int b, int c, int& x, int& y) {
  int d = egcd(a, b, x, y);
  if (c%d) return false;
  y = ((-y*c/d)%(a/d) + (a/d))%(a/d);
  x = (c + b*y)/a;
  return true;
}

Usages:

  * Check Relative primeness egcd(a,b,dummy, dummy) == 1
  * Modular Inverse of a (mod n) if (egcd(a,b,x,y) == 1) return x; else return ERROR;


-- Main.MatthewChan - 13 Jan 2006