Modular Exponentiation in Logarithmic Time

Problem

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

Sample Input

a = 2, b = 3, p = 5

Sample Output

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;
}

Output

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));

 }

}

Output

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))

Output

3

People are also reading:

• Count subarrays with given XOR
• Longest Substring without repeating characters
• Find MSB in O(1)
• Nth root of M
• Find K-th Smallest Element in BST
• In-place vs out-of-place algorithms
• Print a two-dimensional view of a Binary Tree
• Subarray with Sum k
• Find Maximum Subarray Sum
• Longest? ?Bitonic? ?Subarray? ?Problem?