SHARE
TWEET

Python Extended Euclidean Algorithm

husoski Oct 14th, 2019 (edited) 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # euclid_demo.py -- Extended Euclidean Algorithm & modular inverse sample use
  2.  
  3. def gcdx(x,y):
  4.     """Returns (r,a,b) where r=GCD(x,y) and a,b are integers with ax+by==r."""
  5.  
  6.     r1, a1, b1 = x, 1, 0
  7.     r2, a2, b2 = y, 0, 1
  8.    
  9.     while r2:
  10.         q, r = divmod(r1, r2)
  11.         r1, a1, b1, r2, a2, b2 = r2, a2, b2, r, a1 - q*a2, b1 - q*b2
  12.     return (r1, a1, b1) if r1 >= 0 else (-r1, -a1, -b1)
  13.  
  14. if __name__=="__main__":
  15.     a = int(input("Enter a: "))
  16.     b = int(input("Enter b: "))
  17.    
  18.     r, s, t = gcdx(a, b)
  19.  
  20.     print("gcdx({},{}) returned r={}, s={}, t={}".format(a, b, r, s, t))
  21.     c = s % b
  22.     print("c = {} % {} = {}".format(s, b, c))
  23.  
  24.     print("({} * {}) % {} = {}".format(a, c, b, (a * c) % b))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top