Modular Multiplicative Inverse

Let us start with few facts and know importance of this topic. While using mod (%) operator,

(a + b) % m = a%m + b%m
(a * b) % m = a%m * b%m

But this relation doesn’t satisfy when performing division.

(a / b) % m ≠ a%m / b%m

Being a commonly used operator, this problem has to be overcome. i.e. to apply mod operator on a division operation. Extended Euclidean algorithm comes to rescue when b,m are co-primes.

When b and m are co-primes, find MI = modular inverse of b over m. This modular inverse can be used to find quotient of division applied to modulus.
i.e

(a / b) % m = a%m * MI%m

Here is the C++ function for finding modular multiplicative inverse using extended euclidean:

int modInv(int b, int m)
{
	int r1 = m,r2 = b;
	int t1 = 0,t2 = 1;
	int q,r,t;
	while(r2 > 0)
	{
		q = r1/r2;
		r = r1 - q*r2;
		r1= r2;
		r2= r;
		t = t1 - q*t2;
		t1 = t2;
		t2 = t;
	}
	if(r1 == 1)
		return t1;
	else
	{
		printf("Inverse doesn't exist");
		return -1;
	}
}

Inverse doesn’t exist only in the cases when b and m are not coprimes.

Fermet’s Little Theorem:
This theorem is saviour to overcome the difficulty in able to remember the Extended Euclidean algorithm. In most of the problems on competitive programming, MOD value is generally a constant prime, usually with a value of 10^9 + 7. Fermet’s Little theorem states that inverse of a number ‘A’ over mod ‘N’, when N is prime is modPow(A,N-2,N). i.e.

A-1 = AN-2 % N

Though the value of N is very large, you can always use Modular Exponentiation Algorithm to solve it efficiently.

Advertisements

Modular Exponentiation Algorithm

In this post I will be discussing a method to find (ab)%MOD. The problem is simple, we have been doing it from long time to find ab. But as b increases, we may think of writing a code for it. Say a simple method like this:

long long int modPow(long long int m, long long int n, long long int mod)
{
    long long int p = 1;
    for(int i = 0;i < n;i++) 
    { 
        p *= m; 
        p %= mod; 
    } 
    return mod; 
}  

Above mentioned function solves the need. But is not efficient. Complexity of the function is O(n) and hence cannot find required answer for large values of b or n(for n values > 108) in reasonable time. This can be optimised using Modular Exponentiation Algorithm. This algo solves the problem in O(log n) complexity. Here is the function:

 
long long int fastModPow(long long int a, long long int b, long long int mod) 
{ 
    long long int ans = 1; 
    while(b > 0)
    {
        if(b%2 == 1)
            ans = (ans*a)%mod;
        a = (a*a)%mod;
        b /= 2;
    }
    return ans;
}

How this function works?
Let us solve for 550. Leave the modulus as it is just an additional operation that is done commonly at each step.

bin(50) = 110010

Initial values    : ans = 1                      a = 5                      b = 50
Step 1            : ans = 1                      a = 5*5                      b = 25
Step 2            : ans = 1 * 52               a = 52 * 52               b = 12
Step 3            : ans = 52                      a = 54 * 54             b = 6
Step 4            : ans = 52                      a = 58 * 58              b = 3
Step 5            : ans = 52 * 516            a = 516 * 516            b = 1
Step 6            : ans = 518 * 532          a = 532 * 532            b = 0

We are left with ans = 550 which is the desired result. As we move from LSB to MSB in binary form of exponent, compare the respective steps shown above. The calculations followed are different for the bit values 1 and 0.