how can I calculate (aa)(aa) modulo n, while
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))
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)