[python]Extended Euclidean Algorithm

I took my exam last night, and I guessed I would fail as I did not know how to calculate extended Euclidean Algorithm required for RSA. I came across this video, which explained eGCD really well, better than the slides I had and the tutor’s explanation, the substitution method explained by my tutor was confusing.

The table to find the GCD, s2 and t2 by hand looks like below:
egcd1

Find GCD with Euclidean Algorithm
In summary gcd is to find the denominator that makes the remainder of two numbers 0. Hence gcd(a, b) = gcd(b, a (mod b)), there will be left shift to test the division until the remainder is 0. So the python equivalent to find the gcd of a and b will be:

def gcd(a, b):
    while b != 0:
        remainder = a % b
        # left shift
        # gcd(a, b) = gcd(b, a (mod b))
        a = b
        b = remainder
    return a

Find s and t with extended Euclidean Algorithm
Thanks to the video, I know how this egcd is done, and hence I wrote my own python logic for this:

def egcd(a, b):
    # thanks to this video: https://www.youtube.com/watch?v=-uFc7-wOplM
    # Extended Euclidean Algorithm assumptions
    # s1 = 1, s2 = 0
    # t1 = 0, t2 = 1
    s1 = 1
    s2 = 0
    t1 = 0
    t2 = 1
    if a < b:
        r1 = b
        r2 = a
    else:
        r1 = a
        r2 = b
    while True:
        quotient = r1 // r2
        remainder = r1 % r2
        # stop when remainder is 0.
        # if there is still remainder continue the process of shifting.
        if remainder != 0:
            s = s1 - s2 * quotient
            t = t1 - t2 * quotient
            # left shift
            r1 = r2
            r2 = remainder
            s1 = s2
            s2 = s
            t1 = t2
            t2 = t
        else:
            gcd = r2
            break
    return gcd, s2, t2

Results
To find gcd of 17 and 667:
egcd2
egcd3

Advertisement

2 thoughts on “[python]Extended Euclidean Algorithm

  1. optimized a bit:

    def egcd(r2, r1):
    # thanks to this video: https://www.youtube.com/watch?v=-uFc7-wOplM
    # Extended Euclidean Algorithm assumptions
    # s1 = 1, s2 = 0
    # t1 = 0, t2 = 1
    s1 = 1
    s2 = 0
    t1 = 0
    t2 = 1
    if r2>r1:
    r1,r2=r2,r1
    while True:
    remainder = r1 % r2
    # stop when remainder is 0.
    # if there is still remainder continue the process of shifting.
    if remainder != 0:
    quotient = r1 // r2
    s = s1 – s2 * quotient
    t = t1 – t2 * quotient
    # left shift
    r1 = r2
    r2 = remainder
    s1 = s2
    s2 = s
    t1 = t2
    t2 = t
    else:
    return r2, s2, t2

  2. optimized a bit:

    def egcd(r2, r1):
    ____# thanks to this video: https://www.youtube.com/watch?v=-uFc7-wOplM
    ____# Extended Euclidean Algorithm assumptions
    ____# s1 = 1, s2 = 0
    ____# t1 = 0, t2 = 1
    ____s1 = 1
    ____s2 = 0
    ____t1 = 0
    ____t2 = 1
    ____if r2>r1:
    ________r1,r2=r2,r1
    ____while True:
    ________remainder = r1 % r2
    ________# stop when remainder is 0.
    ________# if there is still remainder continue the process of shifting.
    ________if remainder != 0:
    ____________quotient = r1 // r2
    ____________s = s1 – s2 * quotient
    ____________t = t1 – t2 * quotient
    ____________# left shift
    ____________r1 = r2
    ____________r2 = remainder
    ____________s1 = s2
    ____________s2 = s
    ____________t1 = t2
    ____________t2 = t
    ________else:
    ____________return r2, s2, t2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s