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

Leave a Reply