# 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... – Chryfi Apr 10 at 21:11
• @πάνταῥεῖ You likely know this but duplicates are different on CR – Sᴀᴍ Onᴇᴌᴀ Apr 10 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 – Sᴀᴍ Onᴇᴌᴀ Apr 16 at 17:17
• While the issues I'd raise with both snippets overlap, I think them sufficiently different to not qualify as duplicates. – greybeard Apr 16 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. – Chryfi Apr 17 at 14:56

Give your variables more meaningful names reflecting their role in the algorithm.

• I'm getting some dejavu here... – Peilonrayz Apr 10 at 20:22
• @Peilonrayz Sure, me too .... – πάντα ῥεῖ Apr 10 at 20:24