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

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

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

| improve this answer | |
  • 1
    \$\begingroup\$ I'm getting some dejavu here... \$\endgroup\$ – Peilonrayz Apr 10 at 20:22
  • \$\begingroup\$ @Peilonrayz Sure, me too .... \$\endgroup\$ – πάντα ῥεῖ Apr 10 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.