section-method-of-repeated-squares.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section4.3The 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

$$\begin{equation*} 2^{2^{1000000} }. \end{equation*}$$

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{equation*} 2^{37398332 } \pmod{ 46389}, \end{equation*}$$

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

$$\begin{equation*} a = 2^{k_1} + 2^{k_2} + \cdots + 2^{k_n}, \end{equation*}$$

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

$$\begin{gather*} a^{2^0} \pmod{ n}\\ a^{2^1} \pmod{ n }\\ \vdots\\ a^{2^k} \pmod{ n}. \end{gather*}$$

Each step involves squaring the answer obtained in the previous step, dividing by $n\text{,}$ and taking the remainder.

Example4.28

We will compute $271^{321} \pmod{ 481}\text{.}$ Notice that

$$\begin{equation*} 321 = 2^0 +2^6 + 2^8; \end{equation*}$$

hence, computing $271^{ 321} \pmod{ 481}$ is the same as computing

$$\begin{equation*} 271^{ 2^0 +2^6 + 2^8 } \equiv 271^{ 2^0 } \cdot 271^{2^6 } \cdot 271^{ 2^8 } \pmod{ 481}. \end{equation*}$$

So it will suffice to compute $271^{ 2^i } \pmod{ 481}$ where $i = 0, 6, 8\text{.}$ It is very easy to see that

$$\begin{equation*} 271^{ 2^1} = \text{73,441} \equiv 329 \pmod{ 481}. \end{equation*}$$

We can square this result to obtain a value for $271^{ 2^2} \pmod{481}\text{:}$

$$\begin{align*} 271^{ 2^2} & \equiv (271^{ 2^1})^2 \pmod{ 481}\\ & \equiv (329)^2 \pmod{ 481}\\ & \equiv \text{108,241} \pmod{ 481}\\ & \equiv 16 \pmod{ 481}. \end{align*}$$

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

$$\begin{equation*} 271^{ 2^6 } \equiv 419 \pmod{ 481} \end{equation*}$$

and

$$\begin{equation*} 271^{ 2^8 } \equiv 16 \pmod{ 481}. \end{equation*}$$

Therefore,

$$\begin{align*} 271^{ 321} & \equiv 271^{ 2^0 +2^6 + 2^8 } \pmod{ 481}\\ & \equiv 271^{ 2^0 } \cdot 271^{ 2^6 } \cdot 271^{ 2^8 } \pmod{ 481}\\ & \equiv 271 \cdot 419 \cdot 16 \pmod{ 481}\\ & \equiv \text{1,816,784} \pmod{ 481}\\ & \equiv 47 \pmod{ 481}. \end{align*}$$

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{.}$