Modular Arithmetic – How to Perform Modulo Arithmetic with Big Numbers

exponentiationmodular arithmetic

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

Best Answer

  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.

Related Question