Tutorialspoint.dev

Modular Exponentiation (Power in Modular Arithmetic)

Given three numbers x, y and p, compute (xy) % p.

Examples :

Input:  x = 2, y = 3, p = 5
Output: 3
Explanation: 2^3 % 5 = 8 % 5 = 3.

Input:  x = 2, y = 5, p = 13
Output: 6
Explanation: 2^5 % 13 = 32 % 13 = 6.
 


We have discussed recursive and iterative solutions for power.

Below is discussed iterative solution.

/* Iterative Function to calculate (x^y) in O(log y) */
int power(int x, unsigned int y)
{
    int res = 1;     // Initialize result
   
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = res*x;
   
        // n must be even now
        y = y>>1; // y = y/2
        x = x*x;  // Change x to x^2
    }
    return res;
}

The problem with above solutions is, overflow may occur for large value of n or x. Therefore, power is generally evaluated under modulo of a large number.



Below is the fundamental modular property that is used for efficiently computing power under modular arithmetic.

(ab) mod p = ( (a mod p) (b mod p) ) mod p 

For example a = 50,  b = 100, p = 13
50  mod 13  = 11
100 mod 13  = 9

(50 * 100) mod 13 = ( (50 mod 13) * (100 mod 13) ) mod 13 
or (5000) mod 13 = ( 11 * 9 ) mod 13
or 8 = 8

Below is the implementation based on above property.

C

// Iterative C program to compute modular power
#include <stdio.h>
  
/* Iterative Function to calculate (x^y)%p in O(log y) */
int power(int x, unsigned int y, int p)
{
    int res = 1;      // Initialize result
  
    x = x % p;  // Update x if it is more than or 
                // equal to p
  
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;
  
        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;  
    }
    return res;
}
  
// Driver program to test above functions
int main()
{
   int x = 2;
   int y = 5;
   int p = 13;
   printf("Power is %u", power(x, y, p));
   return 0;
}

Java

// Iterative Java program to 
// compute modular power
import java.io.*;
  
class GFG {
      
    /* Iterative Function to calculate
       (x^y)%p in O(log y) */
    static int power(int x, int y, int p)
    {
        // Initialize result
        int res = 1;     
         
        // Update x if it is more  
        // than or equal to p
        x = x % p; 
      
        while (y > 0)
        {
            // If y is odd, multiply x
            // with result
            if((y & 1)==1)
                res = (res * x) % p;
      
            // y must be even now
            // y = y / 2
            y = y >> 1
            x = (x * x) % p; 
        }
        return res;
    }
  
    // Driver Program to test above functions
    public static void main(String args[])
    {
        int x = 2;
        int y = 5;
        int p = 13;
        System.out.println("Power is " + power(x, y, p));
    }
}
  
// This code is contributed by Nikita Tiwari.

Python3

# Iterative Python3 program
# to compute modular power
  
# Iterative Function to calculate
# (x^y)%p in O(log y) 
def power(x, y, p) :
    res = 1     # Initialize result
  
    # Update x if it is more
    # than or equal to p
    x = x %
  
    while (y > 0) :
          
        # If y is odd, multiply
        # x with result
        if ((y & 1) == 1) :
            res = (res * x) % p
  
        # y must be even now
        y = y >> 1      # y = y/2
        x = (x * x) % p
          
    return res
      
  
# Driver Code
  
x = 2; y = 5; p = 13
print("Power is ", power(x, y, p))
  
  
# This code is contributed by Nikita Tiwari.

C#

// Iterative C# program to 
// compute modular power
class GFG 
{
  
/* Iterative Function to calculate
(x^y)%p in O(log y) */
static int power(int x, int y, int p)
{
    // Initialize result
    int res = 1;     
      
    // Update x if it is more 
    // than or equal to p
    x = x % p; 
  
    while (y > 0)
    {
        // If y is odd, multiply 
        // x with result
        if((y & 1) == 1)
            res = (res * x) % p;
  
        // y must be even now
        // y = y / 2
        y = y >> 1; 
        x = (x * x) % p; 
    }
    return res;
}
  
// Driver Code
public static void Main()
{
    int x = 2;
    int y = 5;
    int p = 13;
    System.Console.WriteLine("Power is "
                              power(x, y, p));
}
}
  
// This code is contributed by mits

PHP

<?php
// Iterative PHP program to 
// compute modular power
  
// Iterative Function to 
// calculate (x^y)%p in O(log y) 
function power($x, $y, $p)
{
    // Initialize result
    $res = 1; 
  
    // Update x if it is more 
    // than or equal to p
    $x = $x % $p
  
    while ($y > 0)
    {
        // If y is odd, multiply
        // x with result
        if ($y & 1)
            $res = ($res * $x) % $p;
  
        // y must be even now
          
        // y = $y/2
        $y = $y >> 1; 
        $x = ($x * $x) % $p
    }
    return $res;
}
  
// Driver Code
$x = 2;
$y = 5;
$p = 13;
echo "Power is ", power($x, $y, $p);
  
// This code is contributed by aj_36
?>


Output :

 Power is 6

Time Complexity of above solution is O(Log y).

Modular exponentiation (Recursive)



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter