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?

  • 0
    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.2011-03-06

3 Answers 3

2

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

8

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.

7

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.

  • 0
    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.2011-03-06