Shahrooz Zr - 1 year ago 52

C++ Question

how can I calculate (a^{a})^{(aa)} modulo *n*, while

`a<1000`

`n<1000`

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

Answer Source

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