Author lschoe
Recipients lschoe, mark.dickinson, pablogsal, rhettinger, skrah, steven.daprano, tim.peters
Date 2019-02-19.14:39:24
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1550587164.58.0.382920510296.issue36027@roundup.psfhosted.org>
In-reply-to
Content
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 arithmetic. I know from working with generations of students and programmers how easy it is to make mistakes here (including lots of mistakes that I made myself;)

One would implement pow() for negative n, anyway, by first computing the modular inverse and then raising it to the power -n. So, to expose the modinv() function to the outside world won't cost much effort.

Modular powers, in particular, are often very confusing. Like for a prime modulus p, all of pow(a, -1,p), pow(a, p-2, p), pow(a, -p, p) are equal to eachother, but a common mistake is to take pow(a, p-1, p) instead. For a composite modulus things get much trickier still, as the exponent is then reduced in terms of the Euler phi function. 

And, even if you are not confused by these things, 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. With modinv() available separately, one would expect --and get-- an efficient implementation with minimal overhead (e.g., not implemented via a complete extended-gcd).
History
Date User Action Args
2019-02-19 14:39:24lschoesetrecipients: + lschoe, tim.peters, rhettinger, mark.dickinson, steven.daprano, skrah, pablogsal
2019-02-19 14:39:24lschoesetmessageid: <1550587164.58.0.382920510296.issue36027@roundup.psfhosted.org>
2019-02-19 14:39:24lschoelinkissue36027 messages
2019-02-19 14:39:24lschoecreate