How to build fast exponentation for modular?

Question

I need to find modular value of some big number which I cannot calculate by calculator (i.e $233^{351} \pmod {853}$. How can I build a fast exponentiation table for this?

Answer 1

You should use the method of "Repeated Squaring."

That is, you compute $$550 \equiv 233^2 \mod 853$$ $$538 \equiv 550^2 \equiv 233^4 \mod 853$$ $$277 \equiv 538^2 \equiv 233^8 \mod 853$$ $$812 \equiv 277^2 \equiv 233^{16} \mod 853$$ $$ \ldots $$

In this way, you increase the powers of $233$ very quickly, and each step is computationally very easy. At the end, you end up multiplying the appropriate numbers together. For example, to compute $233^{30} \mod 853$, you would multiply $$233^{16} \cdot 233^8 \cdot 233^4 \cdot 233^2 \equiv 812 \cdot 277 \cdot 538 \cdot 500 \mod 853$$

You might notice that for this, we are using the binary expansion of the exponent. In binary, $30 = (11110)_2$, which is why we used the 2nd, 3rd, 4th, and 5th repeated squares to get $233^{30}$.

Does that make sense?