Section 4.3 The Method of Repeated Squares
Computing large powers can be very time-consuming. Just as anyone can compute \(2^2\) or \(2^8\text{,}\) everyone knows how to compute
However, such numbers are so large that we do not want to attempt the calculations; moreover, past a certain point the computations would not be feasible even if we had every computer in the world at our disposal. Even writing down the decimal representation of a very large number may not be reasonable. It could be thousands or even millions of digits long. However, if we could compute something like
we could very easily write the result down since it would be a number between \(0\) and \(46{,}388\text{.}\) If we want to compute powers modulo \(n\) quickly and efficiently, we will have to be clever. 4 
The first thing to notice is that any number \(a\) can be written as the sum of distinct powers of \(2\text{;}\) that is, we can write
where \(k_1 \lt k_2 \lt \cdots \lt k_n\text{.}\) This is just the binary representation of \(a\text{.}\) For example, the binary representation of 57 is 111001, since we can write \(57 = 2^0 + 2^3 + 2^4 + 2^5\text{.}\)
The laws of exponents still work in \({\mathbb Z}_n\text{;}\) that is, if \(b \equiv a^x \pmod{ n}\) and \(c \equiv a^y \pmod{ n}\text{,}\) then \(bc \equiv a^{x+y} \pmod{ n}\text{.}\) We can compute \(a^{2^k} \pmod{ n}\) in \(k\) multiplications by computing
Each step involves squaring the answer obtained in the previous step, dividing by \(n\text{,}\) and taking the remainder.
Example 4.28.
We will compute \(271^{321} \pmod{ 481}\text{.}\) Notice that
hence, computing \(271^{ 321} \pmod{ 481}\) is the same as computing
So it will suffice to compute \(271^{ 2^i } \pmod{ 481}\) where \(i = 0, 6, 8\text{.}\) It is very easy to see that
We can square this result to obtain a value for \(271^{ 2^2} \pmod{481}\text{:}\)
We are using the fact that \((a^{2^n})^2 \equiv a^{2 \cdot 2^n} \equiv a^{ 2^{n+1} } \pmod{ n}\text{.}\) Continuing, we can calculate
and
Therefore,
The method of repeated squares will prove to be a very useful tool when we explore RSA cryptography in Chapter 7. To encode and decode messages in a reasonable manner under this scheme, it is necessary to be able to quickly compute large powers of integers mod \(n\text{.}\)