# Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?

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

• Truly an insightful and thoughtful comment... Thank you Ricky, for your insight. Sep 6 '17 at 19:41

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.

• @Gautam how would the factoring algorithm be?
– Mr.
Sep 7 '17 at 12:21

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

Here is link to solution that uses Fast Exponentiation

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

• This is exactly the algorithm #2 from the answer by D.W., except that you only formulated it for primes. Feb 16 at 20:09
• The question explicitly says the factorization of $n$ is unknown, which may rule out choosing $n$ to be prime. Feb 18 at 19:41
• 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 Feb 19 at 5:44