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

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