Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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?

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.