<p>Sorry if this answer doesn't tell anything nontrivial, but you don't seem to imply these results in the questionm.</p>

<p>Consider first the problem of computing a <strong>modular exponentiation</strong> $ a^r \mod m $.  </p>

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

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

<p>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 $.  </p>

<p>This case of the faster method comes up when you want to evaluate an <strong>exponential tower</strong> $ 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.  </p>

CC BY-SA 3.0
2015-06-19T23:58:23.330Z
Thanks Zsban. I am looking for general algorithms in this case where the factorization of the modulus may not be known. That's not to say this isn't a good addition. Thank you for the write-up.
Ross Snider
CC BY-SA 3.0
2015-06-20T00:09:47.617Z
I think the algorithm is relevant, because it's useful for computing a modular tetration $ a\uparrow\uparrow h \mod m $ where $ h $ and $ m $ are of comparable size.  You asked about tetration in the question, which is why I thought this was relevant.  There could of course be a nontrivial algorithm for tetration that's significantly faster than this, in which case maybe this isn't relevant afterall, but I don't know of such an algorithm.
Zsbán Ambrus
CC BY-SA 3.0
2015-06-20T00:15:31.197Z
Absolutely it is relevant in the case the factorization of the modulus is known. +1 :)
Ross Snider
CC BY-SA 3.0
2015-06-20T07:51:25.430Z
For tetration, note also that the iterated Euler function $\phi^{(h)}(m)$ converges to $1$ after $\sim\log m$ iterations, and in particular, $a\uparrow\uparrow h\bmod m$ is constant (as a function of $h$) for $h\ge\log m$ or so. Thus, you won’t need more than $O(\log m)$ factorizations. One can easily generalize this to the modular Ackermann function; the argument in http://mathoverflow.net/a/165938 is not written with complexity in mind so the bounds are wasteful, but if you think about what really happens there, you’ll see that tetration is actually the hardest case.
Emil Jeřábek
CC BY-SA 3.0
2015-06-20T15:07:58.623Z
@Jeřábek: Wow, I didn't realize that the moduluses go to 1 so quickly.  That's even better than I thought.
Zsbán Ambrus
CC BY-SA 3.0
2015-06-20T16:41:27.073Z
For others curious about this, that result about the iterated Euler phi function is given (with a short proof) in: S. Sivasankaranarayana Pillai, "On a function connected with $\phi(n)$", Bull. Amer. Math. Soc., **35*/6, p. 837–841, (1929), metadata with full text available at http://projecteuclid.org/euclid.bams/1183493597
Zsbán Ambrus
CC BY-SA 3.0
2015-06-19T23:51:54.583Z
2015-06-19T23:51:54.583Z
Zsbán Ambrus
<p>The complexity of modular addition is known: $g + p \mod N$ (for $|p| \approx |g| \approx |N|$) can be computed in $O(n = |N|)$.</p>

<p>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)$.</p>

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

<p>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 <em>h</em>?</p>

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

CC BY-SA 3.0
2015-06-19T22:48:50.933Z
Your notation seems unclear.  What does $ n $ mean in $ O(M(n)k) $?  Is $ n $ the modulus?
Zsbán Ambrus
CC BY-SA 3.0
2015-06-19T23:15:29.200Z
I did take a shortcut in notation, though it is standard and should be understandable based on the context of the question. n is the length of the input (number of digits in the modulus).
Ross Snider
CC BY-SA 3.0
2015-06-19T23:24:47.917Z
Edited the comment to specify $n = |N|$. Thank you for helping to clarify. Please let me know if the question needs some additional clarification.
Ross Snider
<comp-number-theory><complexity>
Computational complexity of modular power towers (tetration)
Ross Snider
# Computational complexity of modular power towers (tetration)

(Asked by: username_0 on 2015-06-19)

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

**Tags:** comp-number-theory, complexity

> **Comments:**
> **username_1**: Your notation seems unclear.  What does $ n $ mean in $ O(M(n)k) $?  Is $ n $ the modulus?  
> **username_0**: I did take a shortcut in notation, though it is standard and should be understandable based on the context of the question. n is the length of the input (number of digits in the modulus).  
> **username_0**: Edited the comment to specify $n = |N|$. Thank you for helping to clarify. Please let me know if the question needs some additional clarification.  

---

## 1 answers

### Answer by username_1 on 2015-06-19. Score: 6

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.

> **Comments:**
> **username_0**: Thanks Zsban. I am looking for general algorithms in this case where the factorization of the modulus may not be known. That's not to say this isn't a good addition. Thank you for the write-up.  
> **username_1**: I think the algorithm is relevant, because it's useful for computing a modular tetration $ a\uparrow\uparrow h \mod m $ where $ h $ and $ m $ are of comparable size.  You asked about tetration in the question, which is why I thought this was relevant.  There could of course be a nontrivial algorithm for tetration that's significantly faster than this, in which case maybe this isn't relevant afterall, but I don't know of such an algorithm.  
> **username_0**: Absolutely it is relevant in the case the factorization of the modulus is known. +1 :)  
> **username_2**: For tetration, note also that the iterated Euler function $\phi^{(h)}(m)$ converges to $1$ after $\sim\log m$ iterations, and in particular, $a\uparrow\uparrow h\bmod m$ is constant (as a function of $h$) for $h\ge\log m$ or so. Thus, you won’t need more than $O(\log m)$ factorizations. One can easily generalize this to the modular Ackermann function; the argument in http://mathoverflow.net/a/165938 is not written with complexity in mind so the bounds are wasteful, but if you think about what really happens there, you’ll see that tetration is actually the hardest case.  
> **username_1**: @Jeřábek: Wow, I didn't realize that the moduluses go to 1 so quickly.  That's even better than I thought.  
> **username_1**: For others curious about this, that result about the iterated Euler phi function is given (with a short proof) in: S. Sivasankaranarayana Pillai, "On a function connected with $\phi(n)$", Bull. Amer. Math. Soc., **35*/6, p. 837–841, (1929), metadata with full text available at http://projecteuclid.org/euclid.bams/1183493597  

---

