I’ve started a cryptography class at DePaul and during the first lecture we first reviewed the Extended Euclidean Algorithm. It provides a method, using only a table, pencil, and paper, to easily find not just the gcd of two integers, but the **s** and **t** values as well. Academically: *Let a and b be two integers, at least one of which is nonzero, and let d = gcd(a,b). There exists some values s,t such that d = sa + tb.*

When it was covered in class, the table didn’t have the **k** column as it does in Wikipedia so I didn’t quite grasp it the first time through. When I’m unsure of something I attempt to write implement it in code. So below is my quick Python implementation of the Extended Euclidean Algorithm for finding **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!

def gcd(a,b,display=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;

# Compute Rows until the GCD is found

while True:

# Calculate a Table Row

s0 = s2 — k1*s1

t0 = t2 — k1*t1

d0 = d2 — k1*d1

k0 = d1/d0

# Shift all the Row Variables

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 display == True:

print “gcd(a,b)=sa+tb: gcd(“+‘a‘+”,”+‘b‘+”)=(“+‘s1‘+”)(“+‘a‘+”)+(“+‘t1‘+”)(“+‘b‘+”) = “+‘d1‘

# Return the results

return d1, s1, t1