[issue36027] Consider adding modular multiplicative inverse to the math module

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

Raymond, I doubt we can do better (faster) than straightforward egcd without heroic effort anyway.  We can't even know whether a modular inverse exists without checking whether the gcd is 1, and egcd builds on what we have to do for the latter anyway.  Even if we did know in advance that a modular inverse exists, using modular exponentiation to find it requires knowing the totient of the modulus, and computing the totient is believed to be no easier than factoring.

The only "optimization" I'd be inclined to _try_ for Python's use is an extended binary gcd algorithm (which requires no bigint multiplies or divides, the latter of which is especially sluggish in Python):

https://www.ucl.ac.uk/~ucahcjm/combopt/ext_gcd_python_programs.pdf

For the rest:

- I'd also prefer than negative exponents other than -1 be supported.  It's just that -1 by itself gets 95% of the value.

- It's fine by me if `pow(a, -1, m)` is THE way to spell modular inverse.  Adding a distinct `modinv()` function too strikes me as redundnt clutter, but not damaging enough to be worth whining about.  So -0 on that.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue36027>
_______________________________________