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

Tim Peters 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

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

Raymond Hettinger added the comment: > +1 for the pow(value, -1, modulus) spelling. It should raise > `ValueError` if `value` and `modulus` are not relatively prime. > It would feel odd to me _not_ to extend this to > `pow(value, n, modulus)` for all negative `n`, again > valid only only if

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

Berry Schoenmakers added the comment: > Is there a clear reason for your expectation that the xgcd-based algorithm > should be faster? Yeah, good question. Maybe I'm assuming too much, like assuming that it should be faster;) It may depend a lot on the constants indeed, but ultimately the

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

Mark Dickinson added the comment: > Then, it should be considerably faster Why would you expect that? Both algorithms involve a number of (bigint) operations that's proportional to log(p), so it's going to be down to the constants involved and the running times of the individual operations.

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

Berry Schoenmakers added the comment: > ... to see `pow(a, p-2, p)` beat a pure Python xgcd for computing the inverse. OK, I'm indeed assuming that modinv() is implemented efficiently, in CPython, like pow() is. Then, it should be considerably faster, maybe like this: >>>

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

Mark Dickinson 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

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

Berry Schoenmakers added the comment: Agreed, extending pow(value, n, modulus) to negative n would be a great addition! To have modinv(value, modulus) next to that also makes a lot of sense to me, as this would avoid lots of confusion among users who are not so experienced with modular

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

Mark Dickinson added the comment: Here's an example of some code in the standard library that would have benefited from the availability of `pow(x, n, m)` for arbitrary negative n: https://github.com/python/cpython/blob/e7a4bb554edb72fc6619d23241d59162d06f249a/Lib/_pydecimal.py#L957-L960

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

Mark Dickinson added the comment: +1 for the pow(value, -1, modulus) spelling. It should raise `ValueError` if `value` and `modulus` are not relatively prime. It would feel odd to me _not_ to extend this to `pow(value, n, modulus)` for all negative `n`, again valid only only if `value` is

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

Raymond Hettinger added the comment: > If it's spelled this way, put the modulus argument last? Yes, that makes sense. > Years ago Guido signed off on spelling this > >pow(value, -1, modulus) +1 ;-) -- ___ Python tracker

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

Tim Peters added the comment: - Some form of this would be most welcome! - If it's spelled this way, put the modulus argument last? "Everyone expects" the modulus to come last, whether in code: x = (a+b) % m x = a*b % m x = pow(a, b, m) or in math: a^(k*(p-1)) =

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

Change by Steven D'Aprano : -- nosy: +steven.daprano ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

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

New submission from Raymond Hettinger : Having gcd() in the math module has been nice. Here is another number theory basic that I've needed every now and then: def multinv(modulus, value): '''Multiplicative inverse in a given modulus >>> multinv(191, 138)