Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

3 Answers

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|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
add comment

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|improve this answer
add comment

$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|improve this answer
add comment

Your Answer

 
discard

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.