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:
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:
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
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