Extended Euclidean Algorithm in Python

The Extended Euclidean Algorithm is a simple extension to the Euclidean Algorithm that in addition to returning the greatest common denominator also gives numbers s and t such that gcd = s * a + t * b.
Specifically, you may want to find 1 = sa + tb which is very useful in cryptography.

The Code

def extended_euclidean(a,b):
    origa = a
    origb = b

    x = 0
    lastx = 1
    y = 1
    lasty = 0

    while b != 0:
        q = a // b
        a, b = b, a % b

        full = "%d = (%d * %d + %d * %d) - %d * (%d * %d + %d * %d) " % ( b, origa, lastx, origb, lasty, q, origa, x, origb, y )
        short = "%d = %d * %d + %d * %d" % ( b, origa, lastx - x * q, origb, lasty - y * q)
        print("%s\t%s\t%s\t%s" % (a, b, full, short))

        x, lastx = (lastx - q * x, x)
        y, lasty = (lasty - q * y, y)

    return (lastx, lasty)

The Output

Take the numbers 120 and 23:

>>> extended_euclidean(120,23)
23  5   5 = (120 * 1 + 23 * 0) - 5 * (120 * 0 + 23 * 1)     5 = 120 * 1 + 23 * -5
5   3   3 = (120 * 0 + 23 * 1) - 4 * (120 * 1 + 23 * -5)    3 = 120 * -4 + 23 * 21
3   2   2 = (120 * 1 + 23 * -5) - 1 * (120 * -4 + 23 * 21)  2 = 120 * 5 + 23 * -26
2   1   1 = (120 * -4 + 23 * 21) - 1 * (120 * 5 + 23 * -26)     1 = 120 * -9 + 23 * 47
1   0   0 = (120 * 5 + 23 * -26) - 2 * (120 * -9 + 23 * 47)     0 = 120 * 23 + 23 * -120
(-9, 47)