We already learned how to find Modular Inverse for a particular number in a previous post, “Modular Multiplicative Inverse“. Today we will look into finding Modular Inverse in a bulk.

Problem

Given $N$ and $M$ ( $N < M$ and $M$ is prime ), find modular inverse of all numbers between $1$ to $N$ with respect to $M$.

Since $M$ is prime and $N$ is less than $M$, we can be sure that Modular Inverse exists for all numbers. Why? Cause prime numbers are coprime to all numbers less than them.

We will look into two methods. Later one is better than the first one.

$O(NlogM)$ Solution

Using Fermat’s little theorem, we can easily find Modular Inverse for a particular number.

$A^{-1} \ \% \ M = bigmod(A,M-2,M)$, where $bigmod()$ is a function from the post “Repeated Squaring Method for Modular Exponentiation“. The function has complexity of $O(logM)$. Since we are trying to find inverse for all numbers from $1$ to $N$, we can find them in $O(NlogM)$ complexity by running a loop.

int inv[SIZE]; ///inv[x] contains value of (x^-1 % m)
for ( int i = 1; i <= n; i++ ) {
    inv[i] = bigmod ( i, m - 2, m );
}

But it's possible to do better.

$O(N)$ Solution

This solution is derived using some clever manipulation of Modular Arithmetic.

Suppose we are trying to find the modular inverse for a number $a$, $a < M$, with respect to $M$. Now divide $M$ by $a$. This will be the starting point.

$M = Q \times a + r$, (where $Q$ is the quotient and $r$ is the remainder)
$M = \lfloor \frac{M}{a} \rfloor \times a + (M \ \% \ a )$

Now take modulo $M$ on both sides.

$0 \equiv \lfloor \frac{M}{a} \rfloor \times a + (M \ \% \ a ) \ \ \ \text{(mod M )}$
$(M \ \% \ a ) \equiv -\lfloor \frac{M}{a} \rfloor \times a \ \ \ \text{(mod M )}$

Now divide both side by $a \times ( M \ \% \ a )$.

$$\frac{M \ \% \ a}{a \times ( M \ \% \ a )} \equiv \frac{- \lfloor \frac{M}{a} \rfloor \times a } { a \times ( M \ \% \ a ) } \ \ \ \text{(mod M)} \\
\therefore a^{-1} \equiv - \lfloor \frac{M}{a} \rfloor \times ( M \ \% \ a )^{-1} \ \ \ \text{(mod M)}$$

The formula establishes a recurrence relation. The formula says that, in order to find the modular inverse of $a$, we need to find the modular inverse of $b = M \ \% \ a$ first.

Since $b = M \ \% \ a$, we can say that its value lies between $0$ and $a-1$. But, $a$ and $M$ are coprime. So $a$ will never fully divide $M$. Hence we can ignore the possibility that $b$ will be $0$. So possible values of $b$ is between $1$ and $a-1$.

Therefore, if we have all modular inverse from $1$ to $a-1$ already calculated, then we can find the modular inverse of $a$ in $O(1)$.

Code

We can now formulate our code.

int inv[SIZE];
inv[1] = 1;
for ( int i = 2; i <= n; i++ ) {
    inv[i] = (-(m/i) * inv[m%i] ) % m;
    inv[i] = inv[i] + m;
}

In line $2$, we set the base case. Modular inverse of $1$ is always $1$. Then we start calculating inverse from $2$ to $N$. When $i=2$, all modular inverse from $1$ to $i-1=1$ is already calculated in array inv[]. So we can calculate it in $O(1)$ using the formula above at line $4$.

At line $5$, we make sure the modular inverse is non-negative.

Next, when $i=3$, all modular inverse from $1$ to $i-1=2$ is already calculated. This is process is repeated until we reach $N$.

Since we calculated each inverse in $O(1)$, the complexity of this code is $O(N)$.

Conclusion

I saw this code first time on CodeChef forum. I didn't know how it worked back then. I added it to my notebook and have been using it since then. Recently, while searching over the net for resources on Pollard Rho's algorithm, I stumbled on an article from Come On Code On which had the explanation. Thanks, fR0DDY, I have been looking for the proof.

Reference

1. forthright48 - Modular Multiplicative Inverse
2. forthright48 - Repeated Squaring Method for Modular Exponentiation
3. Come On Code On - Modular Multiplicative Inverse

Problem

Given value of $A$ and $M$, find the value of $X$ such that $AX \equiv 1 \ \text{(mod M)}$.

For example, if $A = 2$ and $M = 3$, then $X = 2$, since $2 \times 2 = 4 \equiv 1 \ \text{(mod 3)}$.

We can rewrite the above equation to this:

$AX \equiv 1 \ \text{(mod M)}$
$X \equiv \frac{1}{A} \ \text{(mod M)}$
$X \equiv A^{-1} \ \text{(mod M)}$

Hence, the value $X$ is known as Modular Multiplicative Inverse of $A$ with respect to $M$.

How to Find Modular Inverse?

First we have to determine whether Modular Inverse even exists for given $A$ and $M$ before we jump to finding the solution. Modular Inverse doesn’t exist for every pair of given value.

Existence of Modular Inverse

Modular Inverse of $A$ with respect to $M$, that is, $X = A^{-1} \text{(mod M)}$ exists, if and only if $A$ and $M$ are coprime.

Why is that?

$AX \equiv 1 \ \text{(mod M)}$
$AX – 1 \equiv 0 \ \text{(mod M)}$

Therefore, $M$ divides $AX-1$. Since $M$ divides $AX-1$, then a divisor of $M$ will also divide $AX-1$. Now suppose, $A$ and $M$ are not coprime. Let $D$ be a number greater than $1$ which divides both $A$ and $M$. So, $D$ will divide $AX – 1$. Since $D$ already divides $A$, $D$ must divide $1$. But this is not possible. Therefore, the equation is unsolvable when $A$ and $M$ are not coprime.

From here on, we will assume that $A$ and $M$ are coprime unless state otherwise.

Using Fermat’s Little Theorem

Recall Fermat’s Little Theorem from a previous post, “Euler’s Theorem and Fermat’s Little Theorem“. It stated that, if $A$ and $M$ are coprime and $M$ is a prime, then, $A^{M-1} \equiv 1 \text{(mod M)}$. We can use this equation to find the modular inverse.

$A^{M-1} \equiv 1 \ \text{(mod M)}$ (Divide both side by $A$)
$A^{M-2} \equiv \frac{1}{A} \ \text{(mod M)}$
$A^{M-2} \equiv A^-1 \ \text{(mod M)}$

Therefore, when $M$ is prime, we can find modular inverse by calculating the value of $A^{M-2}$. How do we calculate this? Using Modular Exponentiation.

This is the easiest method, but it doesn’t work for non-prime $M$. But no worries since we have other ways to find the inverse.

Using Euler’s Theorem

It is possible to use Euler’s Theorem to find the modular inverse. We know that:

$A^{\phi(M)} \equiv 1 \text{(mod M)}$
$\therefore A^{\phi(M)-1} \equiv A^{-1} \text{(mod M)}$

This process works for any $M$ as long as it’s coprime to $A$, but it is rarely used since we have to calculate Euler Phi value of $M$ which requires more processing. There is an easier way.

Using Extended Euclidean Algorithm

We are trying to solve the congruence, $AX \equiv 1 \text{(mod M)}$. We can convert this to an equation.

$AX \equiv 1 \text{(mod M)}$
$AX + MY = 1$

Here, both $X$ and $Y$ are unknown. This is a linear equation and we want to find integer solution for it. Which means, this is a Linear Diophantine Equation.

Linear Diophantine Equation can be solved using Extended Euclidean Algorithm. Just pass $\text{ext_gcd()}$ the value of $A$ and $M$ and it will provide you with values of $X$ and $Y$. We don’t need $Y$ so we can discard it. Then we simply take the mod value of $X$ as the inverse value of $A$.

Code

$A$ and $M$ need to be coprime. Otherwise, no solution exists. The following codes do not check if $A$ and $M$ are coprime. The checking is left of the readers to implement.

When $M$ is Prime

We will use Fermat’s Little Theorem here. Just call the $bigmod()$ function from where you need the value.

int x = bigmod( a, m - 2, m ); // (ax)%m = 1

Here $x$ is the modular inverse of $a$ which is passed to $bigmod()$ function.

When $M$ is not Prime

For this, we have to use a new function.

int modInv ( int a, int m ) {
    int x, y;
    ext_gcd( a, m, &x, &y );

    // Process x so that it is between 0 and m-1
    x %= m;
    if ( x < 0 ) x += m;
    return x;
}

I wrote this function since after using $\text{ext_gcd()}$ we need to process $x$ so that it's value is between $0$ and $M-1$. Instead of doing that manually, I decided to write a function.

So, if we want to find the modular inverse of $A$ with respect to $M$, then the result will be $X = modInv ( A, M )$.

Complexity

Repeated Squaring method has a complexity of $O(logP)$, so the first code has complexity of $O(logM)$, whereas Extended Euclidean has complexity of $O(log_{10}A+log_{10}B)$ so second code has complexity $O(log_{10}A + log_{10}M)$.

Why Do We Need Modular Inverse?

We need Modular Inverse to handle division during Modular Arithmetic. Suppose we are trying to find the value of the following equations:

$\frac{4}{2} \ \% \ 3$ - This is simple. We just simplify the equation and apply normal modular operation. That is, it becomes $\frac{4}{2} \ \% \ 3 = 2 \ \% \ 3 = 2$.

Then what happens when we try to do same with $\frac{12}{9}\ \% \ 5$? First we simply. $\frac{12}{9}\ \% \ 5 = \frac{4}{3}\ \% \ 5$. Now we are facing an irreducible fraction. Should we simply perform the modular operation with numerator and denominator? That doesn't help since both of them are smaller than $5$.

This is where Modular Inverse comes to the rescue. Let us solve the equation $X \equiv 3^{-1} \ \text{(mod 5)}$. How do we find the value of $X$? We will see that on the later part of the post. For now, just assume that we know the value of $X$.

Now, we can rewrite the above equation in the following manner:

$\frac{12}{9}\ \% \ 5$
$\frac{4}{3}\ \% \ 5$
$(4 \times 3^{-1})\ \% \ 5$
$( (4\ \% \ 5) \times (3^{-1}\ \% \ 5) ) \ \% \ 5$
$\therefore 4X \ \% \ 5$

So, now we can easily find the value of $\frac{A}{B} \ \% \ M$ by simply calculating the value of $(A \times B^{-1}) \ \% \ M$.

Conclusion

Modular Inverse is a small topic but look at the amount of background knowledge it requires to understand it! Euler's Theorem, Euler Phi, Modular Exponentiation, Linear Diophantine Equation, Extended Euclidian Algorithm and other small bits of information. We covered them all before, so we can proceed without any hitch.

Hopefully, you understood how Modular Inverse works. If not, make sure to revise the articles in the "Reference" section below.

Reference

1. Wiki - Modular Multiplicative Inverse
2. forthright48 - Euler's Theorem and Fermat's Little Theorem
3. forthright48 - Modular Exponentiation
4. forthright48 - Euler Phi
5. forthright48 - Linear Diophantine Equation
6. forthright48 - Extended Euclidean Algorithm