Extended Euclidean Algorithm to find Modular Multiplicative Inverse

Modular multiplicative inverse of a number a mod m is a number x such that

ax ≡ 1 (mod m)

It is very helpful where division is carried out along with modular operation. Instead of dividing by a number, its inverse can be multiplied to fetch the same result i.e.

k/a mod m = k*x mod m

Modular multiplicative inverse can be find only if the two numbers are coprimes i.e. their gcd is 1.
Here we are using Extended Euclidean Algorithm to find the inverse.

The algorithm is same as Euclidean algorithm to find gcd of two numbers. Euclid’s algorithm starts with the given two integers and forms a new pair that consists of the smaller number and the remainder of the division of larger number with smaller number numbers. The new pair again applied given algorithm until the remainder is zero. The only extension in extended euclidean algorithm is that every divisor and remainder is represented as linear combination of the original two numbers and coefficients are stored in every iteration.

Algorithm:

We have to find x such that ax ≡ 1 (mod m)
Above equivalence can be stated alternatively as:
ax  = pm + 1
or ax + my = 1 known as Bézout’s identity.

The beginning two numbers are a and m
x and y are coefficients of a and m respectively when dividend is represented as linear combination of a and m.
u and v are coefficients of a and m respectively when divisor is represented as linear combination of a and m.
c and d are coefficients of a and m respectively when remainder is represented as linear combination of a and m.

Initially dividend is m and divisor is a
m = 0*a + 1*m = x*a + y*m
a = 1*a + 0*m = u*a + v*m
So x = 0, y = 1, u = 1, v = 0

m = q*a + r where q is quotient and r is remainder.
From next iteration q  acts as dividend and r as divisor. Let e is dividend and f is divisor in iteration.

e = q*f + r
r = (-q)*f + 1*e = (-q)*(u*a + v*m) + 1*(x*a + y*m) = (x – u*q)*a + (y – v*q)*m

So
c = x – u*q
d = y – v*q
For next iteration roles will be switched as:
f is dividend ⇒ e = f
r is divisor ⇒ f = r
x = u
y = v
u = c
v = d

Termination:

When r is 1
r = c*a + d*m = 1
c is the required modular inverse.

Example:

Consider example of two numbers  a = 29, m = 168

29x + 168y = 1
168 = 0*29  + 1*168                          
29   = 1*29 + 0*168                         

First Step:
168 = 5*29 + 23    
23 = (-5)*29 + 1*168 = (-5)*[1*29 + 0*168] + 1*[0*29  + 1*168]

Second Step:
29 = 1*23 + 6
6 = 1*29 + (-1) *23 = 1*[0*168 + 1*29] + (-1)*[(-5)*29 + 1*168] = 6*29 + (-1)*168

Third Step:
23 = 3*6 + 5
5 = 1*23 + (-3)*6 = 1*[ (-5)*29 + 1*168] + (-3)*[6*29 + (-1)*168] = (-23)*29 + 4*168

Fourth Step:
6 = 1*5 + 1
1 = (-1)*5 + 1*6 = (-1)*[(-23)*29 + 4*168] + 1*[6*29 + (-1)*168] = 29*29 + (-5)*168

Hence final solution comes as:
29*29 + (-5)*168 = 1
x = 29 and y = (-5)

C/C++ Implementation:


int modmulinverse(int a,int m)
{
    int x = 0,y = 1,u = 1,v = 0; 
    int e = m,f = a;
    int c,d,q,r;
    while(f != 1)
    {
        q = e/f;
        r = e%f;
        c = x-q*u;
        d = y-q*v;
        x = u;
        y = v;
        u = c;
        v = d;
        e = f;
        f = r;
    } 
    u = (u+m)%m;
    return u;
}
About these ads

2 comments on “Extended Euclidean Algorithm to find Modular Multiplicative Inverse

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s