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$?
-
$\begingroup$ Truly an insightful and thoughtful comment... Thank you Ricky, for your insight. $\endgroup$ – Gautam Sep 6 '17 at 19:41
There are essentially only two algorithms that I'm aware of:
Use repeated-squaring, along the lines you mentioned.
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.
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} $
-
5$\begingroup$ This is exactly the algorithm #2 from the answer by D.W., except that you only formulated it for primes. $\endgroup$ – Emil Jeřábek Feb 16 at 20:09
-
$\begingroup$ The question explicitly says the factorization of $n$ is unknown, which may rule out choosing $n$ to be prime. $\endgroup$ – Geoffrey Irving Feb 18 at 19:41
-
$\begingroup$ 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 $\endgroup$ – Bhaskar13 Feb 19 at 5:44