Shahrooz Zr Shahrooz Zr - 4 months ago 15
C++ Question

Calculate (a^a)^(a^a) modulo n

how can I calculate (aa)(aa) modulo n, while


If share source code of this problem in C++, I will really appreciate.


Firstly, to exponentiate large numbers in remainder class rings (i.e. modulo something), there exist some iterative algorithms, foremost Square and Multiply. The basic idea is to do either squaring or multiplying in a step. Then reduce modulo n and continue. This way, you will never have too large numbers.

The second optimization that can be done is due to the Fermat-Euler Theorem, which says that

(a^b) mod n = a^(b mod phi(n))

where phi(n) is Euler's totient function iff a and n are co-prime.

Knowing this, we can analyze your expression a bit closer:


So, in pseudo-code, this looks as follows:

input a, n
a := a mod n
phin := totient(n)
phiphin := totient(phin)
exp2 := (a + 1) mod phiphin
exp := powMod(a mod phin, exp2, phin) //implements square and multiply for a^b mod n
result := powMod(a, exp, n)