# Python extended Euclidean algortihm + inverse modulo

I programmed the extended Euclidean algorithm together with the inverse modulo because I am making an RSA system from scratch. Any feedback regarding efficiency etc. is welcome :)

    def ext_gcd(a, b):

a0, a1 = a, b
x0, x1 = 1, 0
y0, y1 = 0, 1

while a1 != 0:
q = a0//a1
r, s, t = a1, x1, y1
a1 = a0 % a1
x1 = x0 - q*x1
y1 = y0 - q*y1
a0, x0, y0 = r, s, t

return x0, y0, a0

def inverse_mod(a, mod):
va, y0, a0 = Math.ext_gcd(a, mod)
return va % mod


• No... the answer given there isn't very time efficient... Commented Apr 10, 2020 at 21:11
• @πάνταῥεῖ You likely know this but duplicates are different on CR Commented Apr 10, 2020 at 21:16
• I'm voting to repoen because while both posts involve the Euclidean algorithm this one also mentions inverse modulo. For context, see meta posts like this and this Commented Apr 16, 2020 at 17:17
• While the issues I'd raise with both snippets overlap, I think them sufficiently different to not qualify as duplicates. Commented Apr 16, 2020 at 22:05
• I also thought that this shouldn't be marked as duplicate... yes me and the other guy have both the same mathematical algorithm but mine is a little bit different and the answers given there... well the one answer at the moment uses the most time inefficient approach I have ever seen and I was asking also for feedback for time efficiency. I would appreciate a reopen. Commented Apr 17, 2020 at 14:56