1
\$\begingroup\$

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

1 Answer 1

Reset to default
2
\$\begingroup\$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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