SB Large Powers of Integers

Section 4.4 Large Powers of Integers

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

2^{2}

2^{8},

everyone knows how to compute

🔗

2^{2^{1000000}} .

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} (\mod 46389),

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 2 (not really).

🔗

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.4.1. Repeated Squares.

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

🔗

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.

🔗

Prev Top Next