GCD is the greatest common divisor. For two integers (\(x\) and \(y\)), the extended GCD method solves \(ax + by = v\) for \(a\) and \(b\), and where \(v=gcd(x,y)\). One example of using the Extended GCD method is to determine the modulo inverse of a value (the inverse value of \(n \pmod p\) so that \(n \cdot n^{-1} = 1 \pmod p\)).
Extended GCD |
Coding
from libnum import gcd,xgcd import sys def _xgcd(a, b): x0, x1, y0, y1 = 0, 1, 1, 0 while a != 0: (q, a), b = divmod(b, a), a y0, y1 = y1, y0 - q * y1 x0, x1 = x1, x0 - q * x1 return x0, y0, b def modinv(a, b): x, _,v = xgcd(a, b) if v != 1: raise Exception('gcd(a, b) != 1') return x % b x=693 y=609 if (len(sys.argv)>1): x=int(sys.argv[1]) if (len(sys.argv)>2): y=int(sys.argv[2]) res = _xgcd(x,y) (a,b,v) = res print (f"x={x}, y={y}\na={a}, b={b}, v={v}") res = xgcd(x,y) (a,b,v) = res print (f"\nChecking with libnum: x={x}, y={y}, a={a}, b={b}, v={v}") result = a*x+b*y print (f"\na*x+b*y={result}") result = gcd(x,y) print (f"gcd(x,y)=={result}") print ("\n\nTry an example of xgcd:") res=modinv(53,120) print (f" Inv 57 mod 97=={res}")
A sample run is:
x=693, y=609 a=-7, b=8, v=21 Checking with libnum: x=693, y=609, a=-7, b=8, v=21 a*x+b*y=21 gcd(x,y)==21 Try an example of xgcd: Inv 57 mod 97==77