# Efficient way to find $a^b \bmod {n}$

I am not sure whether or not this is a duplicate question. I'm wondering what is an efficient way to compute $$x \equiv a^b \bmod{n}$$ where $a,b,n \in \mathbb{Z}$ and $a,b < n$?

For example say I need to compute $13^{59} \bmod{77}$, how do I do it manually?

-
Manually? Why? –  TonyK Mar 6 '11 at 7:29
@TonyK : Because in exams we are not allowed to use a computer. :) BTW this is a homework question. –  Prasoon Saurav Mar 6 '11 at 7:30
By the way, there's no need for any restriction on $a$ or $b$, though you can take $a$ modulo $n$ and $b$ modulo $\phi(n)$. –  Yuval Filmus Mar 6 '11 at 7:32
If this is for exam purpose, you may want to use Chinese Remainder Theorem to split your modulus. In your example, considering mod 7 or 11 + Euler's theorem is not a lot of work. –  Soarer Mar 6 '11 at 7:35

The usual trick is repeated squaring. If you want to raise a number $x$ to the 59th power, you follow this algorithm:

x1 = x
x2 = x1 * x1
x4 = x2 * x2
x8 = x4 * x4
x16 = x8 * x8
x32 = x16 * x16
x59 = x32 * x16 * x8 * x2 * x1


Usually the algorithm is given using the following recurrence equations: $$x^{2n} = (x^n)^2, x^{2n+1} = (x^n)^2\cdot x.$$ Using these equations, you can write a function that raises a number to a power.

Since you're computing everything modulo $n$, don't forget to reduce modulo $n$ each time. This will keep the numbers small and so the effort manageable.

-
Knuth (in TAOCP) discusses this at length - repeated squaring is not optimal, though it uses at most twice as many multiplications as necessary, and a lot of squarings, which may be a bit faster. –  Yuval Filmus Mar 6 '11 at 7:34

This case is rather simple, since $(13,77)=1$ and $\phi(77) = 60$. So by Euler's theorem $13^{60} \equiv 1 \pmod{77}$. Now $13^{59}\cdot 13 \equiv 1 \pmod{77}$, Hence you can find it using the generalized Euclidean algorithm.

In general if $(a,n)=1$, then I'd take $b \pmod{\phi(n)}$ and proceed with taking iterated squares.

-
$13^{59} \pmod 7 = (-1)^{59} \pmod 7 = 6$.
$13^{59} \pmod {11} = 2^{59} \pmod {11} = 2^9 \pmod {11} = 6$.
So the answer is $6$.