Algorithm Implementation/Mathematics/Extended Euclidean algorithm

From Wikibooks, open books for an open world
Jump to: navigation, search

Python[edit]

Both functions take positive integers a, b as input, and return a triple (g, x, y), such that ax + by = g = gcd(a, b).

Iterative algorithm[edit]

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

Recursive algorithm[edit]

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

Modular inverse[edit]

An application of extended GCD algorithm to finding modular inverses:

def modinv(a, m):
    gcd, x, y = egcd(a, m)
    if gcd != 1:
        return None  # modular inverse does not exist
    else:
        return x % m

Haskell[edit]

Unextended[edit]

euclid :: Integral a => a -> a -> a
euclid 0 b = abs b
euclid a 0 = abs a
euclid a b = euclid b $ rem a b

Extended[edit]

eGCD :: Integral a => a -> a -> (a,a,a)
eGCD a 0 = (a, 1, 0)
eGCD a b = let (g, x, y) = eGCD b $ rem a b
           in (g, y, x - (a `div` b) * y)
-- Does not work, test case 1245 (-1603) fails.