# Extended Euclidean Algorithm

I’ve started a cryp­tog­ra­phy class at DePaul and dur­ing the first lec­ture we first reviewed the Extended Euclid­ean Algo­rithm.  It pro­vides a method, using only a table, pen­cil, and paper, to eas­ily find not just the gcd of two inte­gers, but the s and t val­ues as well. Aca­d­e­m­i­cally: Let a and b be two inte­gers, at least one of which is nonzero, and let d = gcd(a,b). There exists some val­ues s,t such that d = sa + tb.

When it was cov­ered in class, the table didn’t have the k col­umn as it does in Wikipedia so I didn’t quite grasp it the first time through.  When I’m unsure of some­thing I attempt to write imple­ment it in code. So below is my quick Python imple­men­ta­tion of the Extended Euclid­ean Algo­rithm for find­ing d, s, and t, given a and b in d = gcd(a,b) = sa + tb . Not quite sure what we’ll use it for, but I have no doubt that I will learn that soon enough!

# Uses the Extended Euclid­ean Algo­rithm (Table Method) to find the gcd, s, and t
def gcd(a,b,dis­play=False):
# Setup the first two rows of the table
s2 = 1; t2 = 0; d2 = a; k2 = 1;
s1 = 0; t1 = 1; d1 = b; k1 = d2/d1;

# Com­pute Rows until the GCD is found
while True:
# Cal­cu­late a Table Row
s0 = s2 — k1*s1
t0 = t2 — k1*t1
d0 = d2 — k1*d1
k0 = d1/d0

# Shift all the Row Vari­ables
d2 = d1;    d1 = d0;
s2 = s1;    s1 = s0;
t2 = t1;    t1 = t0;
k2 = k1;    k1 = k0;

# We’ve found the GCD
if d2%d1 == 0:
break

# Print the Results
if dis­play == True:
print “gcd(a,b)=sa+tb: gcd(“+‘a‘+”,”+‘b‘+”)=(“+‘s1‘+”)(“+‘a‘+”)+(“+‘t1‘+”)(“+‘b‘+”) = “+‘d1‘

# Return the results
return d1, s1, t1