In Wikipedia, Graham's number, it is described how to calculate the last d digits of Graham's number. They introduce an algorithm simply iterating
$$x = 3^x \mod 10^d$$
d times starting with x=3.
What slightly confuses me : To calculate a power $a^b \mod n$ , $a$ must be reduced mod $n$, but $b$ must be reduced mod $\phi(n)$.
As, for example $\phi(1000)=400$ , reducing modulo $1000$ and reducing modulo $400$ is the same, if only the last TWO digits have to be calculated. Is this the reason, that the height of the power tower must be by one greater than the number of digits to calculate ? Or did I miss something else ?
To generalize the problem. How do I properly calculate
$$a \uparrow \uparrow b \mod n$$
for natural numbers $a$, $b$, $n$ ?