Computational complexity of modular power towers (tetration)
Sorry if this answer doesn't tell anything nontrivial, but you don't seem to imply these results in the questionm.

Consider first the problem of computing a modular exponentiation $ a^r \mod m $.  

You say above that you can compute this by repeated squaring modulo $ m $, and that this needs $ O(\log r) $ multiplications.  This is true, and it's certainly a practical algorithm for some range of inputs.  But for other inputs, it's not the best you can do. The important case I want to talk about comes up when $ r $ is very large.

First, let $ c = gcd(a, m) $ and $ b = a/c $ and we'll compute the result as the product of the $ c^r \mod m $ and $ b^r \mod m $ values.  If $ \log_2 m &lt; r $ then $ c^r \equiv 0 $, otherwise computer $ c^r $ by the simple algorithm with $ \log r $ multiplications.  Now we need a number $ s $ such that $ b^s \equiv 1 $, from which we can compute $ b^r $ as $ b^{r \mod s} $.  The Euler phi function $ s = \varphi(m) $ is such a number.  To compute $ s $, you need the integer factorization of $ m $, which takes $ O(m^\epsilon) $ time.  

If the exponent $ r $ is so large that even $ \log r $ is significantly greater than $ m $, then reducing the exponent this way gives a faster method for the modular exponentiation.  Alternately, if you have a problem where the inputs are constrained so you always know the factorization of $ m $, such as if you take only prime or power of two exponents, then this method is worth already when $ r $ is significantly greater than $ m $.  

This case of the faster method comes up when you want to evaluate an exponential tower $ a^{r^t} \mod m $, supposing $ t $ is significantly larger than $ m $.  For this, first compute $ s = \varphi(m) $ like above, then compute $ r^t \mod s $ by some modular exponentiation algorithm, then compute $ a^{r^t} $ as above.  As $ r^t $ is large, this is faster than the simple method of first computing $ r^t $ and then doing $ O(\log(r^t)) $ modular multiplications.  You can apply this to any exponential tower, thus recursively computing the exponential tower modulo $ m $.  If you have an exponential tower of at least four levels and the final exponent is of comparable size to $ m $, such as in a tetration, then it is very likely that the logarithm of final exponent will be much greater than $ m $, so again this method is worth to compute a tetration.