Modular multiplicative inverse function in Python

Question

Does some standard Python module contain a function to compute modular multiplicative inverse of a number  i e  a number y   invmod x  p  such that x y    1  mod p   Google doesn t seem to give any good hints on this   Of course  one can come up with home-brewed 10-liner of extended Euclidean algorithm  but why reinvent the wheel   For example  Java s BigInteger has modInverse method  Doesn t Python have something similar

User · Answer

As of 3 8 pythons pow   function can take a modulus and a negative integer  See here  Their case for how to use it is    gt  gt  gt  pow 38  -1  97  23  gt  gt  gt  23   38   97    1 True

User · Answer

Well  I don t have a function in python but I have a function in C which you can easily convert to python  in the below c function extended euclidian algorithm is used to calculate inverse mod   int imod int a int n   int c i 1  while 1       c   n   i   1      if c a  0           c   c a          break            i      return c     Python Function  def imod a n     i 1   while True      c   n   i   1      if c a  0         c   c a       break      i   i 1    return c   Reference to the above C function is taken from the following link C program to find Modular Multiplicative Inverse of two Relatively Prime Numbers

User · Answer

I try different solutions from this thread and in the end I use this one   def egcd a  b       lastremainder  remainder   abs a   abs b      x  lastx  y  lasty   0  1  1  0     while remainder          lastremainder   quotient  remainder    remainder  divmod lastremainder  remainder          x  lastx   lastx - quotient x  x         y  lasty   lasty - quotient y  y     return lastremainder  lastx    -1 if a  lt  0 else 1   lasty    -1 if b  lt  0 else 1    def modinv a  m       g  x  y   self egcd a  m      if g    1          raise ValueError  modinv for    does not exist  format a       return x   m   Modular inverse in Python

User · Answer

Here is my code  it might be sloppy but it seems to work for me anyway     a is the number you want the inverse for   b is the modulus  def mod inverse a  b       r   -1     B   b     A   a     eq set          full set          mod set            euclid s algorithm     while r  1 and r  0          r   b a         q   b  a         eq set    r  b  a  q -1          b   a         a   r         full set append eq set       for i in range 0  4           mod set append full set -1  i        mod set insert 2  1      counter   0       extended euclid s algorithm     for i in range 1  len full set            if counter 2    0              mod set 2    full set -1  i 1   3  mod set 4  mod set 2              mod set 3    full set -1  i 1   1           elif counter 2    0              mod set 4    full set -1  i 1   3  mod set 2  mod set 4              mod set 1    full set -1  i 1   1           counter    1      if mod set 3     B          return mod set 2  B     return mod set 4  B

User · Answer

Sympy  a python module for symbolic mathematics  has a built-in modular inverse function if you don t want to implement your own  or if you re using Sympy already    from sympy import mod inverse  mod inverse 11  35    returns 16 mod inverse 15  35    raises ValueError   inverse of 15  mod 35  does not exist    This doesn t seem to be documented on the Sympy website  but here s the docstring  Sympy mod inverse docstring on Github

User · Answer

Here is a one-liner for CodeFights  it is one of the shortest solutions   MMI   lambda A  n s 1 t 0 N 0   n  lt  2 and t N or MMI n  A n  t  s-A  n t  N or n  -1  n lt 1    It will return -1 if A has no multiplicative inverse in n   Usage   MMI 23  99    returns 56 MMI 18  24    return -1   The solution uses the Extended Euclidean Algorithm

User · Answer

Python 3 8  y   pow x  -1  p   Python 3 7 and earlier Maybe someone will find this useful  from wikibooks   def egcd a  b       if a    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 does not exist       else          return x   m

User · Answer

from the cpython implementation source code   def invmod a  n       b  c   1  0     while n          q  r   divmod a  n          a  b  c  n   n  c  b - q c  r       at this point a is the gcd of the original inputs     if a    1          return b     raise ValueError  Not invertible     according to the comment above this code  it can return small negative values  so you could potentially check if negative and add n when negative before returning b

User · Answer

To figure out the modular multiplicative inverse I recommend using the Extended Euclidean Algorithm like this   def multiplicative inverse a  b       origA   a     X   0     prevX   1     Y   1     prevY   0     while b    0          temp   b         quotient   a b         b   a b         a   temp         temp   X         a   prevX - quotient   X         prevX   temp         temp   Y         Y   prevY - quotient   Y         prevY   temp      return origA   prevY

User · Answer

Many of the links above are broken as for 1 23 2017   I found this implementation  https   courses csail mit edu 6 857 2016 files ffield py

User · Answer

You might also want to look at the gmpy module  It is an interface between Python and the GMP multiple-precision library  gmpy provides an invert function that does exactly what you need    gt  gt  gt  import gmpy  gt  gt  gt  gmpy invert 1234567  1000000007  mpz 989145189    Updated answer  As noted by  hyh   the gmpy invert   returns 0 if the inverse does not exist  That matches the behavior of GMP s mpz invert   function  gmpy divm a  b  m  provides a general solution to a bx  mod m     gt  gt  gt  gmpy divm 1  1234567  1000000007  mpz 989145189   gt  gt  gt  gmpy divm 1  0  5  Traceback  most recent call last     File   lt stdin gt    line 1  in  lt module gt  ZeroDivisionError  not invertible  gt  gt  gt  gmpy divm 1  4  8  Traceback  most recent call last     File   lt stdin gt    line 1  in  lt module gt  ZeroDivisionError  not invertible  gt  gt  gt  gmpy divm 1  4  9  mpz 7    divm   will return a solution when gcd b m     1 and raises an exception when the multiplicative inverse does not exist   Disclaimer  I m the current maintainer of the gmpy library   Updated answer 2  gmpy2 now properly raises an exception when the inverse does not exists    gt  gt  gt  import gmpy2   gt  gt  gt  gmpy2 invert 0 5  Traceback  most recent call last     File   lt stdin gt    line 1  in  lt module gt  ZeroDivisionError  invert   no inverse exists

User · Answer

If your modulus is prime  you call it p  then you may simply compute   y   x   p-2  mod p    Pseudocode   Or in Python proper   y   pow x  p-2  p    Here is someone who has implemented some number theory capabilities in Python  http   www math umbc edu  campbell Computers Python numbthy html  Here is an example done at the prompt   m   1000000007 x   1234567 y   pow x m-2 m  y 989145189L x y 1221166008548163L x y   m 1L

User · Answer

Here is a concise 1-liner that does it  without using any external libraries     Given 0 lt a lt b  returns the unique c such that 0 lt c lt b and a c    gcd a b   mod b     In particular  if a b are relatively prime  returns the inverse of a modulo b  def invmod a b   return 0 if a  0 else 1 if b a  0 else b - invmod b a a  b  a   Note that this is really just egcd  streamlined to return only the single coefficient of interest

User · Answer

The code above will not run in python3 and is less efficient compared to the GCD variants  However  this code is very transparent  It triggered me to create a more compact version   def imod a  n    c   1  while  c   a  gt  0        c    n  return c    a

[python] Modular multiplicative inverse function in Python

Examples related to python

Examples related to algorithm