# How to build fast exponentation for modular?

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?

-
See my answer here: math.stackexchange.com/questions/296073/computing-large-powers/… Regards – Amzoti Feb 11 '13 at 2:46
Check for efficient exponentiation algorithms, like the binomial ones. Or just use GNU's bc(), or a computer algebra package (probably wolframalpha.com can do it for you). For programs, look for multiprecision packages like gmp. – vonbrand Feb 11 '13 at 3:04
Azmoti/mixedmath's solution is a good one for a general case. It can also be done recursively, which would be useful if you wanted to do it as part of a computer program. It is technically possible to do it in fewer multiplications. I can do it in 12, but there may be a solution in 11 I'm not seeing. – Mike Feb 11 '13 at 3:12

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?

-
I kinda get a concept of repeated squaring, now I need to apply it and do it myself – REALFREE Feb 11 '13 at 3:03
What if an exponent is like 233? Its binary is 11011111 then I need to use 1th to 5th and 7,8th? if a binary is like 10000001 do I still need to calculate intermediate value to get next step? – REALFREE Feb 11 '13 at 3:14
@REALFREE: Yes, that's exactly right. You still need the calculations, and you take only the binary parts you need. – mixedmath Feb 11 '13 at 3:16