Modular PowersLet us compute 1143 (mod 13). As we saw before we start with squaring this number: 112 (mod 13) = 121 (mod 13) = 4 (mod 13) 114 (mod 13) = (112)2 (mod 13) = 42 (mod 13) = 16 (mod 13) = 3 (mod 13) 118 (mod 13) = (114)2 (mod 13) = 32 (mod 13) = 9 (mod 13) 1116 (mod 13) = (118)2 (mod 13) = 92 (mod 13) = 81 (mod 13) = 3 (mod 13) 1132 (mod 13) = (1116)2 (mod 13) = 32 (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 round-off 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 300-digit power modulo a 300-digit number is very fast.
|