Modular Exponentiation in Logarithmic Time

Posted in

Modular Exponentiation in Logarithmic Time
vinaykhatri

Vinay Khatri
Last updated on March 19, 2024

    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:

    Leave a Comment on this Post

    0 Comments