AATA The Method of Repeated Squares

Section 4.3 The Method of Repeated Squares

Computing large powers can be very time-consuming. Just as anyone can compute

2^{2}

2^{8},

everyone knows how to compute

2^{2^{1,000,000}} .

🔗

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^{37,398,332} (\mod 46,389),

🔗

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 Chapter 7

🔗

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

a = 2^{k_{1}} + 2^{k_{2}} + \dots + 2^{k_{n}},

🔗

where

k_{1} < k_{2} < \dots < 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

Z_{n};

that is, if

b \equiv a^{x} (\mod n)

and

c \equiv a^{y} (\mod n),

then

b c \equiv a^{x + y} (\mod n) .

We can compute

a^{2^{k}} (\mod n)

k

multiplications by computing

\begin{matrix} a^{2^{0}} (\mod n) \\ a^{2^{1}} (\mod n) \\ ⋮ \\ a^{2^{k}} (\mod n) . \end{matrix}

🔗

Each step involves squaring the answer obtained in the previous step, dividing by

n,

and taking the remainder.

🔗

Example 4.28.

🔗

We will compute

271^{321} (\mod 481) .

Notice that

321 = 2^{0} + 2^{6} + 2^{8};

🔗

hence, computing

271^{321} (\mod 481)

is the same as computing

271^{2^{0} + 2^{6} + 2^{8}} \equiv 271^{2^{0}} \cdot 271^{2^{6}} \cdot 271^{2^{8}} (\mod 481) .

🔗

So it will suffice to compute

271^{2^{i}} (\mod 481)

where

i = 0, 6, 8 .

It is very easy to see that

271^{2^{1}} = 73,441 \equiv 329 (\mod 481) .

🔗

We can square this result to obtain a value for

271^{2^{2}} (\mod 481) :

\begin{aligned} 271^{2^{2}} & \equiv (271^{2^{1}})^{2} (\mod 481) \\ \equiv (329)^{2} (\mod 481) \\ \equiv 108,241 (\mod 481) \\ \equiv 16 (\mod 481) . \end{aligned}

🔗

We are using the fact that

(a^{2^{n}})^{2} \equiv a^{2 \cdot 2^{n}} \equiv a^{2^{n + 1}} (\mod n) .

Continuing, we can calculate

271^{2^{6}} \equiv 419 (\mod 481)

🔗

and

271^{2^{8}} \equiv 16 (\mod 481) .

🔗

Therefore,

\begin{aligned} 271^{321} & \equiv 271^{2^{0} + 2^{6} + 2^{8}} (\mod 481) \\ \equiv 271^{2^{0}} \cdot 271^{2^{6}} \cdot 271^{2^{8}} (\mod 481) \\ \equiv 271 \cdot 419 \cdot 16 (\mod 481) \\ \equiv 1,816,784 (\mod 481) \\ \equiv 47 (\mod 481) . \end{aligned}

🔗

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 .

Prev Top Next