Section 4.4 Large Powers of Integers
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 \(2^{37398332 } \pmod{ 46389}\text{,}\) 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. 1
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
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.4.1. Repeated Squares.
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. 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{.}\)
Remark 4.4.2. Sage.
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.