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 43 = 64 so, 2^64(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 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 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. |
Python3
# 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 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 // a Prime Number $A = 3; $B = 9; $C = 4; $M = 19; echo Calculate( $A , $B , $C , $M ); // This code is contributed // by ajit ?> |
Javascript
<script> // Javascript 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) { // Initialize result let 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; } function Calculate(A, B, C, M) { let 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 a Prime Number let A = 3, B = 9, C = 4, M = 19; document.write(Calculate(A, B, C, M)); </script> |
Output:
18
Time Complexity: O(log(B) + log(C))
Auxiliary space: O(1)