Tuesday, September 29, 2015

Modular Inverse from 1 to N

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/a) * inv[m%a] ) % 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 till 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

Saturday, September 26, 2015

Euler Phi Extension and Divisor Sum Theorem

Previously we learned about Euler Phi Function. Today we are going to look at two theorems related to Euler Phi that frequently appears in CPPS. I am not sure whether these theorems have any official names, so I just made them up. These allow easy references so I will be using these names from now on.


Euler Phi Extension Theorem

Theorem: Given a number $N$, let $d$ be a divisor of $N$. Then the number of pairs $\{a,N\}$, where $1 \leq a \leq N$ and $gcd(a,N) = d$, is $\phi(\frac{N}{d})$.

Proof

We will prove the theorem using Euler Phi Function and Arithmetic notion.

We need to find the numbe of pairs $\{a,N\}$ such that $gcd(a,N) = d$, where $1 \leq a \leq N$. 

Both $a$ and $N$ are divisible by $d$ and $d$ is the GCD. So, if we divide both $a$ and $N$ by $d$, then they will no longer have any common divisor.

$gcd(\frac{a}{d},\frac{N}{d}) = 1$,  where $1 \leq a \leq N$.

We know that the possible values of $a$ lie in range $1 \leq a \leq N$. What about the possible values of $\frac{a}{d}$? $\frac{a}{d}$ must lie between $1  \leq \frac{a}{d} \leq \frac{N}{d}$ otherwise $a$ will cross its limit.

Therefore, $gcd(a,N) = d$, where $1 \leq a \leq N$ is same as, $gcd(\frac{a}{d},\frac{N}{d}) = 1$, where $1  \leq \frac{a}{d} \leq \frac{N}{d}$.

So all we need to do is find the value of  $gcd(\frac{a}{d},\frac{N}{d}) = 1$, where $1  \leq \frac{a}{d} \leq \frac{N}{d}$.

Let $N' = \frac{N}{d}$ and $a' = \frac{a}{d}$. How many pairs of $\{a',N'\}$ are there such that $gcd(a',N') = 1$ and $1 \leq a' \leq N'$? Isn't this what Euler Phi Function finds? The answer is $\phi(N') = \phi(\frac{N}{d})$.

Euler Phi Divisor Sum Theorem

Theorem: For a given integer $N$, the sum of Euler Phi of each of the divisors of $N$ equals to $N$, i.e, $$N = \sum_{d|N}\phi(d)$$

Proof

The proof is simple. I have broken down the proof in the following chunks for the ease of understanding.

Forming Array $A$

Imagine, we the following fractions in a list: $$\frac{1}{N}, \frac{2}{N}, \frac{3}{N}...\frac{N}{N}$$

Not very hard to imagine right? Let us convert this into an array of pairs. So now, we have the following array $A$: 

$$A = [ \{1,N\},\{2,N\},\{3,N\}...\{N,N\} ]$$

So we have an array of form $\{a,N\}$, where $a$ is between $1$ and $N$. There are exactly $N$ elements in the array.

Finding GCD of Pairs

Next, we find the GCD of each pair, $g$. What are the possible values of $g$? Since $g$ must divide both $a$ and $N$, $g$ must be a divisor of $N$. Therefore, we can conclude that, GCD of pair $\{a,N\}$ will be one of the divisors of $N$.

Let the divisors of $N$ be the following: $d_1, d_2, d_3...d_r$. So these are the only possible GCD.

Forming Parititions

Next, we form partitions $P_i$. Let us put all pairs which have $gcd(a,N) = d_i$ to partition $P_i$. Therefore, we will have $R$ partitions, where $R$ is the number of divisor of $N$. Note that each pair will belong to one partition only since a pair has a unique GCD. Therefore, $$N = \sum_{i=1}^{R}P_i$$

Size of Each Paritition

How many elements does partition $P_i$ contain? $P_i$ has all the pairs $\{a,N\}$ such that $gcd(a,N) = d_i$, $1 \leq a \leq N$. Using Euler Phi Extension Theorem from above, this value is $\phi(\frac{N}{d_i})$.

Wrapping it Up

We are almost done with the proof. Since $N = \sum_{i=1}^{R}P_i$, we can now write: $$N = \sum_{i=1}^{R}P_i = \sum_{i=1}^{R}\phi(\frac{N}{d_i})$$

But $d_i$ is just a divisor of $N$. So we can simplify and write:

$$N = \sum_{d|N}\phi(\frac{N}{d}) = \sum_{d|N}\phi(d)$$

Conclusion

These theorems may look so simple that you might think they are useless. Especially Euler Phi Divisor Sum Theorem, $N = \sum_{d|N} \phi(d)$. How is this useful at all? Hopefully, we will see one of its application on next post.

Reference

Wednesday, September 23, 2015

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\times2 = 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