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