Modular Exponentiation (Power in Modular Arithmetic) in C++

In this tute, we will discuss Modular Exponentiation (Power in Modular Arithmetic) in C++.

Given 3 integers a, b, and m, find (ab) % m. Let’s see how to calculate (ab) % m in Time complexities O(b) and O(log2b).

Here, we will use two properties of modular arithmetic.

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

 

(ab) % m in O(b) time complexity:

In this method, we run a loop for b times which multiples a each time to the result res. As a result, we get (ab) % m in b iterations.

Following is an iterative function to find (ab) % m in O(b) time,

int power(int a, int b)
{
    int res = 1;
    a = a % m;
    for(int i=1 ; i<=b ; ++i)
        res = (res * a) % m;
    
    return res;
}

 

(ab) % m in O(log2b) time complexity (Modular Exponentiation):

Recursive approach:

Let’s try to analyze the situation with an example.

For a = 2, b = 22,

222 = 211 x 211

211  = 25 x 25 x 2

25 = 22 x 22 x 2

22 = 21 x 21

21 = 20 x 20 x 2

We computer the value of ax/2 each time till x becomes 0. As a result, we get (ab) % m in log2b iterations each time.

Following is a recursive function to find (ab) % m in O(log2b) time,

int power(int a, int b)
{
    if(b == 0) return 1;

    a = a % m;
    int temp = power(a, b/2);
    if(b&1)
        return (((temp * temp) % m) * a) % m;
    else
        return (temp * temp) % m;
}

Iterative approach:

In this method, we will use binary representations of the numbers a and b. In the previous example, we can see that 222 has a relation to the binary representation of the number 22 which is ‘10110’.

 

When we see the binary representation of 22, we can split it into distinct powers of two. That is,

222 = 2 ^ ((1 x 24) + (0 x 23) + (1 x 22) + (1 x 21) + (0 x 20))

= 2 ^ (24 + 22 + 21)

= 22^4 x 22^2 x 22^1

Let’s see the example once again along with their binary representations.

        A                        B                    RES
     21 (2)              22 (10110)            0 (0)
     22 (4)              11 (1011)              4 (22)
    24 (16)              5 (101)               64 (24 x 22)
    28 (256)             2 (10)                64 (24 x 22)
   216 (65536)        1 (1)         4194304 (216 x 25 x 22)

When we take a look at this, we can see a pattern occurring. At each step, we see that the value of a is squared while the value of b is divided by 2. Similarly, we can generalize this concept for any a and b. While calculating (ab) % m, we can simply take modulo at each multiplication step.

Below is a code Modular Exponentiation (Power in Modular Arithmetic) in C++,

#include<bits/stdc++.h>
using namespace std;

int powerMod(int a, int b, int m)
{
    int res = 1;

    a = a % m;
    while(b>0)
    {
        if(b&1)
            res = (res * a) % m;
        
        a = a * a;
        b = b >> 1;
    }

    return res;
}

int main()
{
    cout<<"(2 pow 22) % 100 = "<<powerMod(2, 22, 100)<<endl;

    cout<<"(3 pow 9) % 5000 = "<<powerMod(3, 9, 5000)<<endl;

    return 0;
}

Output:

(2 pow 22) % 100 = 4
(3 pow 9) % 5000 = 4683

Time complexity:

The time complexity is O(log2b)  because the loop runs through the binary representation of b every time.

 

Finally, If you have any queries or doubts related to Modular Exponentiation (Power in Modular Arithmetic) in C++, simply comment in the comment section provided below.

Also, read:

Leave a Reply

Your email address will not be published. Required fields are marked *