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
asked Apr 10, 2020 at 20:09
\$\endgroup\$
5
  • 1
    \$\begingroup\$ No... the answer given there isn't very time efficient... \$\endgroup\$ Commented Apr 10, 2020 at 21:11
  • 1
    \$\begingroup\$ @πάνταῥεῖ You likely know this but duplicates are different on CR \$\endgroup\$ 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\$ 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\$ 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\$ Commented Apr 17, 2020 at 14:56

1 Answer 1

2
\$\begingroup\$

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

answered Apr 10, 2020 at 20:14
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I'm getting some dejavu here... \$\endgroup\$ Commented Apr 10, 2020 at 20:22
  • \$\begingroup\$ @Peilonrayz Sure, me too .... \$\endgroup\$ Commented Apr 10, 2020 at 20:24

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.