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?
 A: 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.
A: 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.
A: $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$.
