Modular PowersLet us compute 11^{43} (mod 13). As we saw before we start with squaring this number: 11^{2} (mod 13) = 121 (mod 13) = 4 (mod 13) 11^{4} (mod 13) = (11^{2})^{2} (mod 13) = 4^{2} (mod 13) = 16 (mod 13) = 3 (mod 13) 11^{8} (mod 13) = (11^{4})^{2} (mod 13) = 3^{2} (mod 13) = 9 (mod 13) 11^{16} (mod 13) = (11^{8})^{2} (mod 13) = 9^{2} (mod 13) = 81 (mod 13) = 3 (mod 13) 11^{32} (mod 13) = (11^{16})^{2} (mod 13) = 3^{2} (mod 13) = 9 (mod 13)
Putting this together (remember that 43 = 32 + 8 + 2 +1), we get
Now we do our usual modular multiplication:
In the applet below you can see the process of calculating modular powers for other numbers. To submit your input you need to click enter in the modulo field. Modular Powers in Detail
In practice, the modular base n can be much larger (for an RSA algorithm one uses numbers n with around 300 digits!), so that we still can have huge numbers. The important thing is that all the tricks we have just seen ensure that once n is fixed, we have a ceiling for exactly how huge the numbers can become that we have to compute with. Given such a ceiling, it is then possible to write computer programs to do all the computations carefully, so that there is never any roundoff error. In practice, the power that is used is comparable with the base (that is it could be 300 digits). But as the number of multiplications is much less than the power itself, the operation of getting a number to a 300digit power modulo a 300digit number is very fast.
