4 ms·

A minor note: pow is able to calculate modulo inverse (pow(a, -1, n)) starting from python3.8.

• tzs 5y ago
  A minor note to your minor note: if you are on an earlier Python but happen to know ϕ(n), you can use Euler's theorem [1] to replace pow(a, -1, n) with pow(a, ϕ(n)-1, n). [1] if a and n are relatively prime then a^ϕ(n) ≡ 1 mod n. Edit: someone replied to this wondering how Python implemented (a, -1, n). I looked into this once, remembered that I found it was reasonable, but did not remember how it actually did it. I took another look to answer that comment, but the comment has been deleted. The answer is that it uses the extended Euclidean algorithm. The function long_invmod in Objects/longobject.c does the deed.
  • deleted 5y ago
    [deleted]
  • vmilner 5y ago
    Yes, I deleted it because I was being an idiot :) I was momentarily thinking pow(a,-1,n) would need to calculate phi(n) internally (a hard thing to do in general) but the EEA will of course do it very cheaply without needing to know phi(n).