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

Popular posts from this blog

java - SNMP4J General Variable Binding Error -

sql server - python to mssql encoding problem -

windows - Python Service Installation - "Could not find PythonClass entry" -