1
$\begingroup$

Given $a^{b^c}\mod p = x$, where $a,b,c$ are real positive integers and $p$ is a prime, what is the most efficient algorithm to compute $x$ (ideally in polynomial time)?

2 Answers 2

2

The first step I would do would to reduce the exponent $b^c$ modulo $p-1$ to get $d$; if you can factor $p-1$ you could use CRT, otherwise just compute. Then compute $a^d$ modulo $p$.

For computing these powers the binary method is an easy and efficient method --- it involves just squaring and multiplying.

  • 0
    This is Fermat's little theorem: if $\gcd(b,m)=1$ then $b^{m-1}\equiv 1 \pmod{m}$.2011-02-14
1

As stated in Apollo's answer, binary method is an efficient method. More precisely, the number of multiplication is a $\Theta(\log n)$ which show that you cannot beat binary method only by a constant factor. For more detail, check about addition-chain multiplication.

Check http://en.wikipedia.org/wiki/Modular_exponentiation for precise definition of binary method.