• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?