algorithm - Modular multiplicative inverse function in Python -
does standard python module contain function compute modular multiplicative inverse of number, i.e. number y = invmod(x, p)
such x*y == 1 (mod p)
? google doesn't seem give hints on this.
of course, 1 can come home-brewed 10-liner of extended euclidean algorithm, why reinvent wheel.
for example, java's biginteger
has modinverse
method. doesn't python have similar?
maybe find useful (from wikibooks):
def egcd(a, b): if == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(a, m): g, x, y = egcd(a, m) if g != 1: raise exception('modular inverse not exist') else: return x % m
Comments
Post a Comment