Modulo arithmetic with big numbers?

I need to calculate $3781^{23947} \pmod{31847}$. Does anyone know how to do it? I can't do it with regular calculators since the numbers are too big. Is there any other easy solutions?

Thanks

-

1. You can always compute $a^n$ by repeated squaring and multiplication, e.g., to get $a^{13}$, you square $a$, multiply the result by $a$, square twice, and multiply again by $a$. The exact sequence of operations is visible in the binary expansion of $n$.

2. You can always prevent the numbers from getting too big by reducing, using the modulus, whenever the numbers exceed the modulus.

-
I'd just like to point out that repeated squaring is not necessarily the fastest way to do this. The more general "addition-chain exponentiation" (en.wikipedia.org/wiki/Addition-chain_exponentiation) can sometimes require less multiplications. However, it's a lot harder to figure out which multiplications to do. –  Michael Lugo May 2 '11 at 0:14

23947=7*11*311. Then $$3781^{23947} = (3781^7)^{11\times 311}$$ Then reduce $3781^7$ modulo 31847 and keep going. Since $3781^7$ is probably too big, you might have to compute it as $$3781\times 3781^6=3781\times (3781^2)^3$$ where again you reduce mod 31847 wherever possible.

-
And what would you do if you couldn't factor the exponent? –  Gerry Myerson May 2 '11 at 0:11
Precisely what I did with the exponent 7? –  dstt May 2 '11 at 0:16
OK. Then why bother factoring? Does it actually make anything better? –  Gerry Myerson May 2 '11 at 0:24
If you have a small factor and your calculator can handle it, then it usually makes things faster. It might also happen, that $3781^7$ is small mod 31847, so that your calculator can still handle that to the power 11... I usually start by factoring for these reasons. –  dstt May 2 '11 at 0:33

I'm not sure if there is a good trick to use. I think the best way to go about it would be to compute it is to write $23947 = 2^{14} + 2^{12} + 2^{11} + 2^{10} + 2^8 + 2^7 + 2^3 + 2 + 1$ and compute $3781^{2^n} \mod 31847$ by repeatedly squaring and taking the modulus. We can then multiply these values $\mod 31847$ to compute the desired value. WolframAlpha says the answer is 6479.

-
I think the answer will be 7458 based on this method. –  IDS-master May 3 '11 at 1:21

Check out Chapter 1 of Dasgupta, Papadimitriou, Vazarani which describes this and other basic arithmetic on large integers. The version linked above is a preprint of the current edition, but it's free. :)

-