Modular Exponentiation

Problem statement

Find the value of $(a^n)$ % $mod$ .

Example

1
Input: a = 2,  n = 3, mod = 3
2
Output: 2
3
2 raise to the power 3 is 8 and 8%3 = 2.

Tages

Maths, bitmask

Solution

Expected Time Complexity: $Log(n)$

Solution:

Lets take $a = 5$ and $b = 6$ .

Further $b$ in binary representation can be written as $(110)_2$

$b = 6 = 2^2 + 2^1 + 2^0*0 = 4 + 2 + 0$

$5^6 = 5^($$^4$$^+$$^2$$^+$$^0$$^) = 5^4*5^2*5^0$

To compute $a^n$ iterate over bits of $n$ , if the $ith$ bit is set then multiple $2^i$ with answer and do answer = answer % mod.

Time Complexity: $log(n)$

C++
Python

1
#include <iostream>
2
using namespace std;
3

4
int ModularExponent(int a, int n, int mod) {
5
    int ans = 1;
6
    while (n > 0) {
7
        int bit = n & 1;
8
        if (bit) {
9
            ans = (ans * a) % mod;
10
        }
11
        n >>= 1;
12
        a = (a * a) % mod;
13
    }
14
    return ans;
15
}
16

17
int main() {
18

19
    int a = 2;
20
    int n = 3;
21
    int mod = 3
22
    cout << ModularExponent(a, n, mod) << "\n";
23
}

1
def ModularExponent(a, n, mod):
2
    ans = 1
3
    while (n > 0):
4
        bit = n & 1
5
        if bit:
6
            ans = (ans * a) % mod
7
        n >>= 1
8
        a *= a
9
        a %= mod
10
    return ans
11

12
print(ModularExponent(2, 3, 3))