- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

In this problem we are given four values A, B, C, M(a prime number). Our task is to Find power of power under mod of a prime.

We simply need to find the value of (A ^ (B ^ C)) (mod M).

**Let’s take an example to understand the problem,**

A = 3, B = 6, C = 2, M = 11

3

(A ^ (B ^ C)) = (3 ^ (6 ^ 2)) = (3 ^ (36))(mod 11) = 3

A simple solution to the problem is by directly calculating the values of the (A ^ (B ^ C)) , which is done by first calculating the value of (B^C) and then (A ^ (B ^ C)) then taking its mod. (B^C) will result in a huge figure storing which can be a task. And the calculation might lead to overflow.

So, a more efficient approach would be using the fermat’s Little Theorem to find the values.

The theorem is,

a^(m-1) = 1 (mod M) where m is a prime number.

Using this we will convert bc of our problem to a number of the form,

x*(M-1) + y, for our given value of M.

Using the fermat's theorem, the part A^(x*(M-1)) becomes 1.

This will reduce the calculation to, finding the value of A^{y}.

The value of y can be calculated as,

B^{c} = x*(M-1) + y

This makes y the remainder left when we divide B^{c} by (M-1),

So, y = B^{c} % (M-1)

This makes the result alot easy as we need to find,

(A ^ ((B^C) %( M-1)) % M

**Program to illustrate the working of our solution,**

#include<iostream> using namespace std; int calcPowerMod(int x, int y, int p) { int powMod = 1; x = x % p; while (y > 0) { if (y & 1) powMod = (powMod*x) % p; y /=2; // y = y/2 x = (x*x) % p; } return powMod; } int findPowerOfPowerMod(int A, int B, int C, int M) { return calcPowerMod(A, calcPowerMod(B, C, M-1), M); } int main() { int A = 3, B = 6, C = 2, M = 11; cout<<"The power of power under modulo is "<<findPowerOfPowerMod(A, B, C, M); return 0; }

The power of power under modulo is 3

- Related Questions & Answers
- Power of a prime number r in n! in C++
- Find power of a number using recursion in C#
- Power of Two in C
- Power of Four in C++
- Reordered Power of 2 in C++
- How to find power of a number in Python?
- How to find power of a matrix in R?
- Find maximum power of a number that divides a factorial in C++
- 8085 program to find nth power of a number
- C++ Program to Calculate Power of a Number
- C/C++ Program to Find sum of Series with n-th term as n power of 2 - (n-1) power of 2
- Power of Three in Python
- Calculating power of a number in MySQL?
- C++ Program to find whether a number is the power of two?
- Program to find Reordered Power of 2 in Python

Advertisements