6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Truly an insightful and thoughtful comment... Thank you Ricky, for your insight. $\endgroup$
    – Gautam
    Sep 6 '17 at 19:41
9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @Gautam how would the factoring algorithm be? $\endgroup$
    – Mr.
    Sep 7 '17 at 12:21
2
$\begingroup$

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

$\endgroup$
3
  • 5
    $\begingroup$ This is exactly the algorithm #2 from the answer by D.W., except that you only formulated it for primes. $\endgroup$ 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$ 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.