# What is an efficient algorithm to compute modular exponentiation of stacked exponents?

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

-

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.

-
That is correct, but could you explain why we calculate b^c mod p-1 ? – Layton Feb 14 '11 at 21:24
This is Fermat's little theorem: if $\gcd(b,m)=1$ then $b^{m-1}\equiv 1 \pmod{m}$. – Apollo Feb 14 '11 at 21:58

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.

-