Modular Exponentiation

Modular exponentiation can be said to be an extension of Binary exponentiation. It is very often used in problem solving to get the exponent within a range that does not cause integer overflow. It is utilised to calculate the exponent modulo to some other prime i.e., (a^b) % p. Modular exponentiation uses the concept of both binary exponentiation and modular arithmetic.

This algorithm uses the concept of binary exponentiation to calculate the power in less time and the formula of modular multiplication as shown in the above section for getting the required value of the exponent.

Below is the implementation of Modular exponentiation:

C++

// C++ program to compute modular power
#include <bits/stdc++.h>
using namespace std;

// Iterative Function to calculate (x^y)%p in O(log y)
int power(long long x, unsigned int y, int p)
{
    int res = 1;

    // Update x if it is more than or equal to p
    x = x % p;

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

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

        // y = y/2
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

// Driver code
int main()
{
    int x = 2, y = 5, p = 13;

    // Function  call
    cout << "Power is " << power(x, y, p);
    return 0;
}

Java

// Java program to compute modular power
import java.io.*;

class GFG {

    // Iterative Function to calculate (x^y) in O(log y)
    static int power(int x, int y, int p)
    {
        int res = 1;

        // Update x if it is more than or equal to p
        x = x % p;

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

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

            // y = y/2
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    // Driver Code
    public static void main(String[] args)
    {
        int x = 2, y = 5, p = 13;

        // Function call
        System.out.print("Power is " + power(x, y, p));
    }
}

Python3

# Python3 program to compute modular power


# Iterative Function to calculate (x^y)%p in O(log y)
def power(x, y, p):

    # Initialize result
    res = 1

    # Update x if it is more than or equal to p
    x = x % p

    # In case x is divisible by p;
    if (x == 0):
        return 0

    while (y > 0):
        # If y is odd, multiply x with result
        if ((y & 1) == 1):
            res = (res * x) % p

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

    return res


# Driver Code
if __name__ == '__main__':
    x = 2
    y = 5
    p = 13

    # Function call
    print("Power is", power(x, y, p))

// C# program to compute modular power
using System;

public class GFG {

    // Iterative Function to calculate (x^y) in O(log y)
    static int power(int x, int y, int p)
    {
        int res = 1;

        // Update x if it is more than or equal to p
        x = x % p;

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

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

            // y = y/2
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    // Driver Code
    static public void Main()
    {
        int x = 2, y = 5, p = 13;

        // Function call
        Console.Write("Power is " + power(x, y, p));
    }
}

Javascript

// Javascript program to compute modular power

// Iterative Function to calculate (x^y)%p in O(log y)
function power(x, y, p)
{
    let res = 1;

    // Update x if it is more than or equal to p
    x = x % p;

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

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

        // y = y/2
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

// Driver Code
let x = 2;
let y = 5;
let p = 13;

// Function call
console.log("Power is " + power(x, y, p));

PHP

<?php
// PHP program to compute modular power

// Iterative Function to calculate (x^y)%p in O(log y)
function power($x, $y, $p)
{
    $res = 1;

    // Update x if it is more than or equal to p
    $x = $x % $p;

    // In case x is divisible by p
    if ($x == 0)
        return 0;

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

        // y = $y/2
        $y = $y >> 1;
        $x = ($x * $x) % $p;
    }
    return $res;
}

// Driver Code
$x = 2;
$y = 5;
$p = 13;

// Function call
echo "Power is ", power($x, $y, $p);
?>

Output

Power is 6

Time Complexity: O(log(y))
Auxiliary Space: O(1)

Mathematical and Geometric Algorithms – Data Structure and Algorithm Tutorials

Mathematical and geometric algorithms stand as powerful tools for solving complex problems. These algorithms use mathematical and geometric principles to efficiently and elegantly manipulate and analyze data. In this tutorial, we will discuss in detail What are Mathematical and Geometrical Algorithms, When to use them, and how to make use of these algorithms in DSA.

Table of Content

What are Mathematical Algorithms?
Use cases of Mathematical Algorithms
Euclid Algorithm
Modular Arithmetic
Binary Exponentiation
Modular Exponentiation
Sieve of Eratosthenes
Other Useful Mathematical Concepts for Competitive Programming (CP)
What are Geometric Algorithms?
Use cases of Geometric Algorithms
Pattern Printing
Convex Hull

Modular Exponentiation

Mathematical and Geometric Algorithms – Data Structure and Algorithm Tutorials

Similar Reads

Contact Us