[issue36027] Consider adding modular multiplicative inverse to the math module
Mark Dickinson
report at bugs.python.org
Tue Feb 19 10:32:02 EST 2019
Mark Dickinson <dickinsm at gmail.com> added the comment:
> it's still a bit subtle that you have to use pow(a, -1,p) instead of pow(a, p-2, p) to let the modular inverse be computed efficiently
That's not 100% clear: the binary powering algorithm used to compute `pow(a, p-2, p)` is fairly efficient; the extended gcd algorithm used to compute the inverse may or may not end up being comparable. I certainly wouldn't be surprised to see `pow(a, p-2, p)` beat a pure Python xgcd for computing the inverse.
----------
_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue36027>
_______________________________________
More information about the Python-bugs-list
mailing list