This section seems a bit out of nowhere, but it’s a computational tool we need in order to perform the RSA encryption algorithm. When we exponentiate a number, we always get a bigger number, and we’ll want to reduce modulo \(m\text{.}\) In this section we give an algorithm that allows us to perform this operation conveniently.
We begin first by showing how to do it "by hand" and then show how to do it using spreadsheet software.
Subsection
We begin by breaking up a number into sums of powers of two. First, a quick refresher table of the first several powers of two:
Table3.5.1.Some small powers of two
\(n\)
\(2^n\)
1
2
2
4
3
8
4
16
5
32
6
64
7
128
8
256
9
512
10
1024
11
2048
12
4096
Example3.5.2.
Find the binary representation of each of the following numbers:
Each time we square a number, the exponent becomes the next power of 2. And because each number can be expressed as a sum of powers of two, we can exploit this fact using a process we’ll call modular exponentiation.
Definition3.5.3.Modular Exponentiation.
Modular exponentiation is the process of repeatedly squaring and reducing a number modulo some integer, and then combining the results to find the required answer.
Example3.5.4.
Here’s a simple, typed example. We’ll find \(37^{82} \pmod{52}\)
Repeatedly square and reduce \(37 \pmod{52}\) six times. This works since \(2^6 = 64\text{,}\) which is the highest power of \(2\) in the binary representation of 82.
Note that it was a coincidence that we got into a loop of 29, 9, 29, ... But this will happen sometimes!
Now pick from the values above those entries which correspond to the binary representation of our desired power, 82. Since \(82 = 64 + 16 + 2\text{,}\) we pick the entries corresponding to \(37^{64}, 37^{16}, \and 37^2\text{:}\)
Second step, we repeatedly square and reduce, starting with 514 a total of 12 times since \(4096 = 2^{12}\text{.}\)
Before we get started, I want to admit that I did bring in a spreadsheet to help out. You’re encouraged to as well! Excel, Google Sheets, and Apple Numbers all have a =MOD(number, modulus) that compute \(\text{number} \modulus \text{modulus}\) I created a table in Excel like this:
count
power of 2
value mod 711
0
2
=MOD(514, 711)
1
2
=MOD(C2*C2, 711)
2
4
=MOD(C3*C3, 711)
Table3.5.6.Sample table in excel
then you click-drag to expand the formula down until your count is 12 and power of 2 is 4096. This tells us the following equivalences, with asterisks marking those values we need to finish the computation:
Finally, we put it all together, bringing back the original expression and substituting what we found.
\begin{align*}
514^{5367} \amp= 514^{4096 + 1024 + 128 + 64 + 32 + 16 + 4 + 2 + 1}\\
\amp= 514^{4096}\cdot514^{1024}\cdot514^{128}\cdot514^{64}\\
\amp\hspace{1em} \cdot514^{32} \cdot514^{16} \cdot514^{4} \cdot514^2 \cdot514^1\\
\amp\equiv 514 \cdot 658 \cdot 487 \cdot 505 \cdot 523 \cdot 388 \cdot 163 \cdot 415 \cdot 514 \pmod{711} \\
\amp \text{multiple two at a time and reduce mod 711 each time}\\
\amp\equiv 694 \pmod{711}
\end{align*}
Why only multiply a couple numbers at a time and reduce? If we multiplied all those numbers on second to last line, we’d get 586869563497917784218400, which is over half of the number of known stars in the universe 3 . Unless you have a really powerful calculator, you’re going to get approximation errors and an incorrect answer!
Here are the numeric answers - but be sure you can do the process!
81
436
22
2.
Now practice as many examples as you need! Make up your own three numbers. Pick your base \(a\text{,}\) your exponent \(e\text{,}\) and your modulus \(m\text{.}\) Compute \(a^e \pmod{m}\) and check your work using the following Sage cell by changing the values a, e, and m in the code and clicking "Evaluate (Sage)".