Author tim.peters
Recipients lschoe, mark.dickinson, pablogsal, rhettinger, skrah, steven.daprano, tim.peters
Date 2019-02-19.19:59:59
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1550606399.4.0.457137990535.issue36027@roundup.psfhosted.org>
In-reply-to
Content
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.
History
Date User Action Args
2019-02-19 19:59:59tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson, steven.daprano, skrah, pablogsal, lschoe
2019-02-19 19:59:59tim.peterssetmessageid: <1550606399.4.0.457137990535.issue36027@roundup.psfhosted.org>
2019-02-19 19:59:59tim.peterslinkissue36027 messages
2019-02-19 19:59:59tim.peterscreate