Modular inverse

From Algorithmist
Jump to: navigation, search

The inverse of a number a modulo m is a number x such that ax\equiv 1\mod {m}. It exists (and is unique if exists) if and only a and m are relatively prime (that is, \gcd(a,m)=1). In particular, if m is a prime, every non-zero element of Z_{m} has an inverse (thus making it an algebraic structure known as field).

Conventionally, the mathematical notation used for inverses is a^{{-1}}\mod {m}.

In modular arithmetic the inverse of a is analogous to the number 1/a in usual real-number arithmetic. If you have a product c=ab, and one of the factors has an inverse, you can get the other factor by multiplying the product by that inverse: a=cb^{{-1}}\mod {m}. Thus you can perform division in ring Z_{m}.

Finding the inverse[edit]

We can rewrite the defining equation of modular inverses as an equivalent linear diophantine equation: ax+my=1. This equation has a solution whenever \gcd(a,m)=1, and we can find such solution (x,y) by means of the extended Euclidean algorithm.

Then a^{{-1}}\equiv x\mod {m}, and also m^{{-1}}\equiv y\mod {a}.

The following Python code implements this algorithm.

# Iterative Algorithm (xgcd)
def iterative_egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q,r = b//a,b%a; m,n = x-u*q,y-v*q # use x//y for floor "floor division"
        b,a, x,y, u,v = a,r, u,v, m,n
    return b, x, y
# Recursive Algorithm
def recursive_egcd(a, b):
    """Returns a triple (g, x, y), such that ax + by = g = gcd(a,b).
       Assumes a, b >= 0, and that at least one of them is > 0.
       Bounds on output values: |x|, |y| <= max(a, b)."""
    if a == 0:
        return (b, 0, 1)
        g, y, x = recursive_egcd(b % a, a)
        return (g, x - (b // a) * y, y)
egcd = iterative_egcd  # or recursive_egcd(a, m)
def modinv(a, m):
    g, x, y = egcd(a, m) 
    if g != 1:
        return None
        return x % m

Alternative algorithm[edit]

If you happen to know \phi (m), you can also compute the inverses using Euler's theorem, which states that a^{{\phi (m)}}\equiv 1\mod {m}. By multiplying both sides of this equation by a's modular inverse, we can deduce that: a^{{-1}}\equiv a^{{\phi (m)-1}}\mod {m}.

And so you can utilize repeated squaring algorithm to quickly find the inverse.

This algorithm can be useful if m is a fixed number in your program (so, you can hardcode a precomputed value of \phi (m)), or if m is a prime number, in which case \phi (m)=m-1. In general case, however, computing \phi (m) is equivalent to factoring, which is a hard problem, so prefer using the extended GCD algorithm.


Suppose we need to calculate {\frac  {a}{b}}\mod {p}. If b and p are co-primes (or if one of them is a prime), then we can calculate the modular inverse b' of b.


{\frac  {a}{b}}\mod {P}\equiv ab'\mod {P}