# Modular Exponentiation in Logarithmic Time

Posted in  Vinay Khatri
Last updated on November 29, 2023

## Problem

Given three integers, a, b, and p. Compute the value of (a b )%p .

#### Sample Input

`a = 2, b = 3, p = 5`

`3`

#### Explanation

`(23)%5 = 8%5 = 3`

### Why study modulo mathematics

Modulo maths is widely used in various problems. For instance, if the answer gives the integer overflow, problem setters use modulo properties to keep the value of the answer in the integer range. Modulo maths is also used in Cryptographic algorithms like RSA.

### Approach

We will use the below property of the modulo operator to solve the problem:

• If a, b and p are three integers, then (ab)%p = ((a%p)(b%p))%p.

We can extend this logic by iterating the given base upto the given exponent. This is because a^b means a is being multiplied by itself b number times. Therefore, the above property can be extended using an iteration.

### Complexity Analysis

The time complexity is O(log(y)) with no extra space required

#### C++ Programming

```#include <iostream>
using namespace std;

int modulo_exp(long long x, unsigned int y, int p)
{
int ans = 1;

x = x % p;

if (x == 0) return 0; // If x is divisible by p

while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
ans = (ans*x) % p;

// y is even now
y = y>>1;
x = (x*x) % p;

}
return ans;
}

int main()
{
int a = 2;
int b = 3;
int p = 5;

cout << modulo_exp(a, b, p);
return 0;
}```

`3`

#### Java Programming

```import java.io.*;

class Solution
{

static int modulo_exp(int x, int y, int p)
{
int ans = 1;

x = x % p;

if (x == 0)
return 0; // If x is divisible by p;

while (y > 0)
{
// If y is odd, multiply x with result
if ((y & 1) != 0)
ans = (ans * x) % p;

// y is even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}

return ans;
}

public static void main(String[] args)
{
int a = 2;
int b = 3;
int p = 5;
System.out.print(modulo_exp(a, b, p));

}

}```

`3`

#### Python Programming

```def modulo_exp(x, y, p) :
ans = 1

x = x % p

if (x == 0) :
return 0

while (y > 0) :
if ((y & 1) == 1) :
ans = (ans * x) % p

# y is now
y = y >> 1   # y = y/2
x = (x * x) % p

return ans

a,b,p= 2,3,5
print(modulo_exp(a, b, p))```

`3`