# 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

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 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

 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)