The Method of Repeated Squares

Computing large powers can be very time-consuming. Just as anyone can compute \(2^2\) or \(2^8\), everyone knows how to compute \[\begin{aligned}\end{aligned}\]. 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 \[\begin{aligned}\end{aligned}\], we could very easily write the result down since it would be a number between \(0\) and \(46{,}388\). If we want to compute powers modulo \(n\) quickly and efficiently, we will have to be clever. The results in this section are needed only in

The first thing to notice is that any number \(a\) can be written as the sum of distinct powers of \(2\); that is, we can write \[\begin{aligned}\end{aligned}\], where \(k_1 \lt k_2 \lt \cdots \lt k_n\). This is just the binary representation of \(a\). For example, the binary representation of \(57\) is \(111001\), since we can write \(57 = 2^0 + 2^3 + 2^4 + 2^5\).

The laws of exponents still work in \({\mathbb Z}_n\); that is, if \(b \equiv a^x \pmod{ n}\) and \(c \equiv a^y \pmod{ n}\), then \(bc \equiv a^{x+y} \pmod{ n}\). We can compute \(a^{2^k} \pmod{ n}\) in \(k\) multiplications by computing \[\begin{aligned}a^{2^0} \pmod{ n} \\ a^{2^1} \pmod{ n } \\ \vdots \\ a^{2^k} \pmod{ n}\end{aligned}\]. Each step involves squaring the answer obtained in the previous step, dividing by \(n\), and taking the remainder.

The method of repeated squares will prove to be a very useful tool when we explore RSA cryptography in . 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\).

Sage support for cyclic groups is a little spotty but we can still make effective use of Sage and perhaps this situation could change soon.

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.