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)?
What is an efficient algorithm to compute modular exponentiation of stacked exponents?
1
$\begingroup$
number-theory
algorithms
2 Answers
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.
-
0This 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.