3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Manually? Why? $\endgroup$
    – TonyK
    Commented Mar 6, 2011 at 7:29
  • $\begingroup$ @TonyK : Because in exams we are not allowed to use a computer. :) BTW this is a homework question. $\endgroup$ Commented Mar 6, 2011 at 7:30
  • $\begingroup$ 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)$. $\endgroup$ Commented Mar 6, 2011 at 7:32
  • $\begingroup$ 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. $\endgroup$
    – user325
    Commented Mar 6, 2011 at 7:35

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Mar 6, 2011 at 7:34
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .