<p>There are essentially only two algorithms that I'm aware of:</p>

<ol>
<li><p>Use repeated-squaring, along the lines you mentioned.</p></li>
<li><p>Factor $n$ using a state-of-the-art algorithm, then use the Chinese remainder thoerem.  If $p$ is prime, you can compute $a^{b^c} \bmod p$ efficiently by computing $b^c \bmod p-1$ using fast exponentiation, call the result $d$, then computing $a^d \bmod p$.  If $n$ is a product of primes, you can combine the results using the Chinese remainder theorem.</p></li>
</ol>

<p>There is believed to be no efficient algorithm for this problem that is faster than these schemes.  I don't know of any proof of that fact, but this assumption is used as a hardness assumption for one scheme in the literature on timelock cryptography (for the special case where $b=2$), and I don't think any faster algorithms are known.</p>

<p>Of course if you let me pick a value of $a$ that has small order modulo $n$, this will be easy.  As another example, if $n$ has a small prime factor $p$ and $a= 0 \pmod{n/p}$, the problem is also trivial.  There are probably multiple special cases that trivialize the problem, but they're probably not very interesting.  If $n$ is a product of two large primes and $a,b,c$ are chosen randomly, the odds of hitting those special cases should be negligibly small.</p>

CC BY-SA 3.0
2017-09-07T12:21:51.370Z
@Gautam how would the factoring algorithm be?
Turbo
CC BY-SA 3.0
2017-09-06T21:24:36.080Z
2017-09-06T21:24:36.080Z
D.W.
<p>Using Fermat theorem, <span class="math-container">$a^p -a = 0 (\mod p) $</span> and if a and p are co-prime, then <span class="math-container">$ a^{p−1} − 1 =1(\mod p) $</span></p>
<p>So if u choose n to be a prime number(say p), then <span class="math-container">$a^{b^c} \mod p = a^{ (b^{c}  \mod (p-1))} \mod p $</span> ,</p>
<p>Then you can use <strong>Fast Exponentiation trick</strong> in two levels, once for <span class="math-container">$b^c \mod p-1 $</span> then for <span class="math-container">$a^{b^c} \mod p $</span></p>
<hr />
<p>I also suggest you to look at <a href="https://cses.fi/problemset/task/1712" rel="nofollow noreferrer">cses task 1712</a></p>
<p>Here is link to <a href="https://cses.fi/paste/818f3827d9b37859131da6/" rel="nofollow noreferrer">solution</a> that uses <a href="https://cp-algorithms.com/algebra/binary-exp.html#toc-tgt-3" rel="nofollow noreferrer">Fast Exponentiation</a></p>
<p>The problem in cses set has much lower limit for c of <span class="math-container">$ 10^9 $</span> (will work for <span class="math-container">$ 10^{18} $</span> too) than <span class="math-container">$ 10^{40} $</span></p>

CC BY-SA 4.0
2021-02-16T20:09:16.303Z
This is exactly the algorithm #2 from the answer by D.W., except that you only formulated it for primes.
Emil Jeřábek
CC BY-SA 4.0
2021-02-18T19:41:41.670Z
The question explicitly says the factorization of $n$ is unknown, which may rule out choosing $n$ to be prime.
Geoffrey Irving
CC BY-SA 4.0
2021-02-19T05:44:46.970Z
Does " a state-of-the-art algorithm" =>Fermat Little theorem?. I answered why a^{b^c} \mod p = a^{ (b^{c}  \mod (p-1))} \mod p which is missing in D.W. I agree this is not complete answer
Bhaskar13
CC BY-SA 4.0
2021-02-16T18:26:30.350Z
2021-02-16T18:34:14.290Z
2021-02-16T18:34:14.290Z
Bhaskar13
<p>I need to quickly evaluate $a^{b^c} \mod n$ where $c$ is pretty big. Using the usual repeated squaring trick, this can be performed in $O(\log(b^c)) = O(c)$ time. In my problem, $c$ is huge, (say, $&gt; 10^{40}$), making this method unappealing. Also, you don't have access to the factorization of $n$, or to $\phi(n)$, so no clever tricks there. Are there any algorithms which run sublinear in $c$? What if I let you pick whatever special values of $a, b, c$ you like, subject to the constraint that none are zero or $\pm 1$, and also $c$ must be above some threshold $M$?</p>

CC BY-SA 3.0
2017-09-06T19:41:44.343Z
Truly an insightful and thoughtful comment... Thank you Ricky, for your insight.
Gautam
<ds.algorithms><cr.crypto-security><nt.number-theory><comp-number-theory>
Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?
Gautam
# Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?

(Asked by: username_0 on 2017-09-06)

I need to quickly evaluate $a^{b^c} \mod n$ where $c$ is pretty big. Using the usual repeated squaring trick, this can be performed in $O(\log(b^c)) = O(c)$ time. In my problem, $c$ is huge, (say, $> 10^{40}$), making this method unappealing. Also, you don't have access to the factorization of $n$, or to $\phi(n)$, so no clever tricks there. Are there any algorithms which run sublinear in $c$? What if I let you pick whatever special values of $a, b, c$ you like, subject to the constraint that none are zero or $\pm 1$, and also $c$ must be above some threshold $M$?

**Tags:** ds.algorithms, cr.crypto-security, nt.number-theory, comp-number-theory

> **Comments:**
> **username_0**: Truly an insightful and thoughtful comment... Thank you Ricky, for your insight.  

---

## 2 answers

### Answer by username_1 on 2017-09-06. Score: 9

There are essentially only two algorithms that I'm aware of:

1. Use repeated-squaring, along the lines you mentioned.
2. Factor $n$ using a state-of-the-art algorithm, then use the Chinese remainder thoerem. If $p$ is prime, you can compute $a^{b^c} \bmod p$ efficiently by computing $b^c \bmod p-1$ using fast exponentiation, call the result $d$, then computing $a^d \bmod p$. If $n$ is a product of primes, you can combine the results using the Chinese remainder theorem.

There is believed to be no efficient algorithm for this problem that is faster than these schemes. I don't know of any proof of that fact, but this assumption is used as a hardness assumption for one scheme in the literature on timelock cryptography (for the special case where $b=2$), and I don't think any faster algorithms are known.

Of course if you let me pick a value of $a$ that has small order modulo $n$, this will be easy. As another example, if $n$ has a small prime factor $p$ and $a= 0 \pmod{n/p}$, the problem is also trivial. There are probably multiple special cases that trivialize the problem, but they're probably not very interesting. If $n$ is a product of two large primes and $a,b,c$ are chosen randomly, the odds of hitting those special cases should be negligibly small.

> **Comments:**
> **username_2**: @username_0 how would the factoring algorithm be?  

---

### Answer by username_3 on 2021-02-16. Score: 2

Using Fermat theorem, $a^p -a = 0 (\mod p) $ and if a and p are co-prime, then $ a^{p−1} − 1 =1(\mod p) $

So if u choose n to be a prime number(say p), then $a^{b^c} \mod p = a^{ (b^{c} \mod (p-1))} \mod p $ ,

Then you can use **Fast Exponentiation trick** in two levels, once for $b^c \mod p-1 $ then for $a^{b^c} \mod p $

---

I also suggest you to look at [cses task 1712](https://cses.fi/problemset/task/1712)

Here is link to [solution](https://cses.fi/paste/818f3827d9b37859131da6/) that uses [Fast Exponentiation](https://cp-algorithms.com/algebra/binary-exp.html#toc-tgt-3)

The problem in cses set has much lower limit for c of $ 10^9 $ (will work for $ 10^{18} $ too) than $ 10^{40} $

> **Comments:**
> **username_4**: This is exactly the algorithm #2 from the answer by username_1, except that you only formulated it for primes.  
> **username_5**: The question explicitly says the factorization of $n$ is unknown, which may rule out choosing $n$ to be prime.  
> **username_3**: Does " a state-of-the-art algorithm" =>Fermat Little theorem?. I answered why a^{b^c} \mod p = a^{ (b^{c}  \mod (p-1))} \mod p which is missing in username_1 I agree this is not complete answer  

---

