Skip to content

Instantly share code, notes, and snippets.

@paiv
Last active August 4, 2021 08:11
Show Gist options
  • Save paiv/a581f02200f3dcdf739ddd8d3b4cdfe6 to your computer and use it in GitHub Desktop.
Save paiv/a581f02200f3dcdf739ddd8d3b4cdfe6 to your computer and use it in GitHub Desktop.
modular multiplicative inverse
def modinv(n, mod):
t, w, r = 0, 1, mod
while n:
(q, n), r = divmod(r, n), n
t, w = w, t - q * w
if r > 1: raise Exception('not invertible ' + repr(n))
if t < 0: t += mod
return t
@paiv
Copy link
Author

paiv commented Aug 4, 2021

Python 3.8: pow(n, -1, mod)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment