Computational complexity of modular power towers (tetration)

Question

The complexity of modular addition is known: $g + p \mod N$ (for $|p| \approx |g| \approx |N|$) can be computed in $O(n = |N|)$.

The complexity of modular multiplication is open though some results are known: by Toom-Cook $g * p \mod N$ can be performed in $O(n^{1.465})$ and by Schönhage–Strassen in $O(n \log n \log \log n)$.

Modular exponentiation can be performed in $O(M(n) k)$ where $M(n)$ is the complexity of multiplication and $k$ is the length in bits of the exponent by the square-and-multiply algorithm.

I am looking for results about the modular arithmetic in general. Are there better complexity results for performing modular exponentiation (over the 'naive' square-and-multiply)? What results are known for modular exponentiation of power towers of height h?

(For $h = 3$: $g^{g^{g}} \mod N$ and for general $h$: $g^{g^{g^{g^{...^g}}}} \mod N$)

Answer 1

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 < 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.