1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
Approach 1: Brute Force Approach
3.2.
Pseudocode
3.3.
C++ implementation
3.3.1.
Complexity
3.4.
Approach 2: Binary exponentiation
3.5.
Pseudocode
3.6.
C++ implementation
3.6.1.
Complexities
3.6.2.
Space complexity
4.
4.1.
What is modular exponentiation method?
4.2.
What is the time complexity of the binary exponentiation method?
4.3.
What should we do if an exponentiation's value is too large to fit in the integer range?
4.4.
What is modulo?
4.5.
Where can binary exponentiation be used?
5.
Conclusion
Last Updated: May 5, 2024

# Modular Exponentiation

Shreya Deep
0 upvote

## Introduction

Exponentiation is a mathematical operation written as ab, which means the value when a is multiplied by itself, b times. Here, a is called the base, and b is called the exponent or the power. GCD of two numbers is the greatest common divisor of the two numbers.

## Problem Statement

Given three integers x,y, and m, find (x^y)%m.

For example:

Input

``x = 2, y = 5, m = 1000000``

Output

``32``

Explanation: We can see that, 2^5 = 32. And 32%1000000 = 32. Thus, the answer is 32.

Also see, Euclid GCD Algorithm

## Solution Approach

### Approach 1: Brute Force Approach

The most straightforward idea is to go by the definition of exponential and multiply a to itself b times. We run a loop for b times and keep multiplying a to answer and taking modulus each time. Also, the answer should be initiated by 1.

### Pseudocode

``````function exponentiation(int a, int b, int m){
for(int i=0;i<b;i++){
}
}``````

### C++ implementation

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

int exponentiation(int a, int b, int m){
for(int i=0;i<b;i++){
}
}

int main()
{
int a = 2;
int b = 5;
int m = 1000000;
cout<<exponentiation(a,b)<<endl;
}``````

Output

``32``

#### Complexity

Time complexity

O(b), where b is the exponent

Reason: Since we’re multiplying a to the answer b times using a loop, the time complexity will be O(b). Taking modulus takes constant time.

Space complexity

O(1)

Reason: All the spaces taken are constant.

### Approach 2: Binary exponentiation

This is the most efficient approach to do modular exponentiation. We need to calculate ab%m, which can also be written as (a2)b/2%m. Notice that computing a2 takes only constant time, and the whole computation steps are reduced to b/2 steps from b steps. Thus, now we need to calculate xb/2, where x  = a2. But, notice that if b is odd, then b/2 will be a decimal, and calculating that is not easy. Also, if b is odd, we can make it even. How? So, xb can be written as x*(xb-1). Thus, whenever we encounter an odd b, multiply x to the answer and reduce the value of b by 1. Then, keep dividing the power by 2 as long as it is even, and keep replacing the base by its square. Keep taking modulus at each step.

### Pseudocode

``````function exponentiation(int a, int b, int m){
while(b>0){
if(b%2==1){
b--;
}
a = (a*a)%m;
b = b/2;
}
}``````

### C++ implementation

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

int exponentiation(int a, int b){
while(b>0){
if(b%2==1){
b--;
}
a = (a*a)%m;
b = b/2;
}
}

int main()
{
int a = 2;
int b = 5;
int m = 1000000;
cout<<exponentiation(a,b,m)<<endl;
}``````

Output

``32``

#### Complexities

Time complexity

O(log2b), where b is the exponent

Reason: Since we’re dividing b by 2 in each step, the total number of steps will be log2b. Taking modulus takes constant time.

#### Space complexity

O(1)

Reason: All the spaces taken are constant.
Check out this problem - Maximum Product Subarray

### What is modular exponentiation method?

Exponentiation is a mathematical operation written as ab, which means the value a is multiplied by itself b times.

### What is the time complexity of the binary exponentiation method?

The time complexity of the binary exponentiation method is log(b), where b is the exponent.

### What should we do if an exponentiation's value is too large to fit in the integer range?

If any answer's value is so large that it can’t fit in the integer range, take its modulo with a prime number. Generally, that prime number is 10^9 + 7.

### What is modulo?

Modulo represents the remainder when a number a is divided by another number b.

### Where can binary exponentiation be used?

Binary exponentiation can efficiently compute Fibonacci numbers and apply a permutation on an array k times.

## Conclusion

This article discussed the approach to solving “Modular exponentiation.” This was a basic problem of number theory. You should solve some more number theory problems to have a good grasp of this topic. Some of these are: number of vehiclesYogesh and primesalien dictionarynth Fibonacci numberjumping numbersminimum jumps, and stocks are profitable

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more?

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!

Live masterclass