2
$\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$
  • $\begingroup$ Truly an insightful and thoughtful comment... Thank you Ricky, for your insight. $\endgroup$ – Gautam Sep 6 '17 at 19:41
5
$\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$
  • $\begingroup$ Thanks, that's what I thought. I'm actually interested in the case when $N$ is a product of two large primes - I wanted to use this for designing a fast integer factorization algorithm :) $\endgroup$ – Gautam Sep 7 '17 at 1:53
  • $\begingroup$ @Gautam how would the factoring algorithm be? $\endgroup$ – T.... Sep 7 '17 at 12:21

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.