Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 7 down vote accepted

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.

share|cite|improve this answer
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.

share|cite|improve this answer

$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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.