Shahrooz Zr Shahrooz Zr - 3 months ago 6
C++ Question

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

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

a<1000
and
n<1000
?

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

Answer

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:

Formula

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)