Calculating Powers Rapidly
We have just seen how to compute products in modular arithmetic (mod n) without ever looking at numbers larger than the square of n.
For powers ax (mod n) there is an even neater trick, which saves a lot of work, especially when x is large (and we'll need that in the RSA encryption algorithm later).
This trick is based on the method of calculating powers independently of modular arithmetic. Suppose we would like to calculate 1143. The straightforward method would be to multiply 11 by 11, then to multiply the result by 11, and so forth. This would require 42 multiplications. We can save a lot of multiplications if we do the following:
First write 43 as a sum of powers of 2:
That means that
The calculation of the sequence 11, 112, 114, 118, 1116, 1132 requires 5 multiplications as each following term is the square of the previous. Now the calculation of the 43rd power requires three more multiplications. So, the trick allowed us to reduce the number of multiplications from 42 to 8.
In case of modular arithmetic each multiplication is done with small numbers as we always reduce them. For example, if we want to compute 1143 (mod 13), we need to do eight multiplications of numbers less than 13.
Note that 1143 is a humongous number. (Can you compare it with the number of seconds since the Big Bang ?)