Tutorialspoint.dev

Find power of power under mod of a prime

Given four numbers A, B, C and M, where M is prime number. Our task is to find ABC (mod M).

Example:

Input  : A = 2, B = 4, C = 3, M = 23
Output : 6
243(mod 23) = 6


A Naive Approach is to calculate res = BC and then calculate Ares % M by modular exponential. The problem of this approach is that we can’t apply directly mod M on BC, so we have to calculate this value without mod M. But if we solve it directly then we will come up with the large value of exponent of A which will definitely overflow in final answer.

An Efficient approach is to reduce the BC to a smaller value by using the Fermat’s Little Theorem, and then apply Modular exponential.

According the Fermat's little
a(M - 1) = 1 (mod M) if M is a prime.

So if we rewrite BC as x*(M-1) + y, then the
task of computing ABC becomes Ax*(M-1) + y
which can be written as Ax*(M-1)*Ay.
From Fermat's little theorem, we know Ax*(M-1) = 1.
So task of computing ABC reduces to computing Ay

What is the value of y?
From BC = x * (M - 1) + y,
y can be written as BC % (M-1)

We can easily use the above theorem such that we can get
A ^ (B ^ C) % M = (A ^ y ) %  M

Now we only need to find two things as:-
1. y = (B ^ C) % (M - 1)
2. Ans = (A ^ y) % M

C++

// C++ program to find (a^b) mod m for a large 'a'
#include<bits/stdc++.h>
using namespace std;
  
// Iterative Function to calculate (x^y)%p in O(log y)
unsigned int power(unsigned int x, unsigned int y, 
                                   unsigned int p)
{
    unsigned 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;
}
  
unsigned int Calculate(unsigned int A, unsigned int B,
                       unsigned int C, unsigned int M)
{
    unsigned int res, ans;
  
    // Calculate B ^ C (mod M - 1)
    res = power(B, C, M-1);
  
    // Calculate A ^ res ( mod M )
    ans = power(A, res, M);
  
    return ans;
}
  
// Driver program to run the case
int main()
{   // M must be be a Prime Number
    unsigned int A = 3, B = 9, C = 4, M = 19;
  
    cout << Calculate(A, B, C, M);
  
    return 0;
}

Java

// Java program to find (a^b) 
// mod m for a large 'a'
import java.util.*;
  
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 % 2 != 0)
        res = (res * x) % p;
  
    // y must be even now
    y = y >> 1; // y = y/2
    x = (x * x) % p;
    }
    return res;
}
  
static int Calculate(int A, int B, int C, int M) {
    int res, ans;
  
    // Calculate B ^ C (mod M - 1)
    res = power(B, C, M - 1);
  
    // Calculate A ^ res ( mod M )
    ans = power(A, res, M);
  
    return ans;
}
  
// Driver code
public static void main(String[] args) {
      
    // M must be be a Prime Number
    int A = 3, B = 9, C = 4, M = 19;
  
    System.out.print(Calculate(A, B, C, M));
}
}
  
// This code is contributed by Anant Agarwal.

Python

# Python program to calculate the ans
def calculate(A, B, C, M):
  
    # Calculate B ^ C (mod M - 1)
    res = pow(B, C, M-1)
  
    # Calculate A ^ res ( mod M )
    ans = pow(A, res, M)
  
    return ans
  
# Driver program to run the case
A = 3
B = 9
C = 4
  
# M must be Prime Number
M = 19
print( calculate(A, B, C, M) )

C#

// C# program to find (a^b) mod m for
// a large 'a'
using System;
  
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 % 2 != 0)
                res = (res * x) % p;
          
            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }
        return res;
    }
      
    static int Calculate(int A, int B, 
                          int C, int M)
    {
        int res, ans;
      
        // Calculate B ^ C (mod M - 1)
        res = power(B, C, M - 1);
      
        // Calculate A ^ res ( mod M )
        ans = power(A, res, M);
      
        return ans;
    }
      
    // Driver code
    public static void Main()
    {
          
        // M must be be a Prime Number
        int A = 3, B = 9, C = 4, M = 19;
      
        Console.Write(Calculate(A, B, C, M));
    }
}
  
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to find 
// (a^b) mod m for a 
// large 'a'
  
// Iterative Function
// to calculate (x^y)%p
// in O(log y)
function power($x, $y, $p)
{
    $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;
}
  
function Calculate($A, $B, $C, $M)
{
    $res; $ans;
  
    // Calculate B ^ C
    // (mod M - 1)
    $res = power($B, $C, $M - 1);
  
    // Calculate A ^ 
    // res ( mod M )
    $ans = power($A, $res, $M);
  
    return $ans;
}
  
// Driver Code
  
// M must be be 
// a Prime Number
$A = 3; $B = 9; 
$C = 4; $M = 19;
  
echo Calculate($A, $B,  
               $C, $M);
  
// This code is contributed
// by ajit
?>


Output:

18

Time Complexity: O(log(B) + log(C))
Auxiliary space: O(1)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter