# On Exponentiation By Squaring, Revisited

I was rereading my post on exponentiation by squaring, and I realized that I had approached it solely from the point of view of a programmer. That was not necessarily my intention, as I wanted to also show how to use this approach to reduce large exponents with just pencil and paper. This follow-up post will use a more hands-on approach.

It happens frequently when dealing with large exponents in cryptography that the expression cannot be computed using a device with insufficient memory, as the exponent could be hundreds or thousands of digits long. So, what to do? We can use modular exponentiation to reduce the number a step at a time into smaller and more manageable magnitudes, that’s what.

Let’s get started!

Exponentiation refresher:

```35 * 7 = 357
35 + 7 = 35 * 37
```

These equivalences become important in reducing large exponents, as we’ll see below.

# Exponentiation by Squaring

Let’s begin with a simple example. Obviously, the exponent is small enough that we could compute it with a calculator, but we’ll do it by hand anyways to illustrate the point (and it’s fun!).

```376 mod 11

1. Reduce using exponentiation by squaring.

31 mod 11 ≡ 3 mod 11

32 mod 11 ≡ 9 mod 11

34 mod 11 ≡ 32+2 mod 11
≡ 32 * 32 mod 11
≡ 9 * 9 mod 11
≡ 81 mod 11
≡ 4 mod 11

38 mod 11 ≡ 34+4 mod 11
≡ 34 * 34 mod 11
≡ 4 * 4 mod 11    <--- We substitute here using the result of 34
≡ 16 mod 11
≡ 5 mod 11

316 mod 11 ≡ 38+8 mod 11
≡ 5 * 5 mod 11
≡ 25 mod 11       <--- Substitute!
≡ 3 mod 11

332 mod 11 ≡ 316+16 mod 11
≡ 3 * 3 mod 11    <--- Substitute!
≡ 9 mod 11

364 mod 11 ≡ 332+32 mod 11
≡ 4 mod 11        <--- Substitute!

- Do the binary expansion of the base10 exponent
- and write the exponent anew, substituting in
- the power of 2s where the bit is 1.
7610 = 0100 11002
364+8+4 mod 11
364 * 38 * 34 mod 11

- Substitute and calculate!
4 * 5 * 4 mod 11
80 mod 11
3 mod 11

2. Reduce by Euler's theorem.

3ϕ(11) ≡ 1 mod 11
310 ≡ 1 mod 11
310*7+6 mod 11
3107 * 36 mod 11
17 * 36 mod 11
729 mod 11
3 mod 11
```

Let’s do another example, and afterwards we’ll go into more detail about what we just did.

Now, let’s take a number that is raised to a large exponent modulus a number `n`:

`717684 mod 58`

Next, we’ll continually reduce the exponent and calculate, further reducing the congruence when we can.

Note that this “large” number is actually rather small when it comes to cryptography!

```71 mod 58 ≡ 7 mod 58

72 mod 58 ≡ 49 mod 58

74 mod 58 ≡ 72+2 mod 58
≡ 72 * 72 mod 58
≡ 49 * 49 mod 58
≡ 2401 mod 58
≡ 23 mod 58

78 mod 58 ≡ 74+4 mod 58
≡ 74 * 74 mod 58
≡ 23 * 23 mod 58
≡ 529 mod 58
≡ 7 mod 58

716 mod 58 ≡ 78+8 mod 58
≡ 78 * 78 mod 58
≡ 7 * 7 mod 58
≡ 49 mod 58
≡ -9 mod 58

732 mod 58 ≡ 716+16 mod 58
≡ 716 * 716 mod 58
≡ -9 * -9 mod 58
≡ 81 mod 58
≡ 23 mod 58

764 mod 58 ≡ 732+32 mod 58
≡ 732 * 732 mod 58
≡ 23 * 23 mod 58
≡ 529 mod 58
≡ 7 mod 58

7128 mod 58 ≡ 764+64 mod 58
≡ 764 * 764 mod 58
≡ 7 * 7 mod 58
≡ -9 mod 58

7256 mod 58 ≡ 7128+128 mod 58
≡ -9 * -9 mod 58
≡ 81 mod 58
≡ 23 mod 58

7512 mod 58 ≡ 7256+256 mod 58
≡ 23 * 23 mod 58
≡ 7 mod 58

71024 mod 58 ≡ 7512+512 mod 58
≡ 7 * 7 mod 58
≡ -9 mod 58

72048 mod 58 ≡ 71024+1024 mod 58
≡ -9 * -9 mod 58
≡ 23 mod 58

74096 mod 58 ≡ 72048+2048 mod 58
≡ 23 * 23 mod 58
≡ 7 mod 58

78192 mod 58 ≡ 74096+4096 mod 58
≡ 7 * 7 mod 58
≡ -9 mod 58

716384 mod 58 ≡ 78192+8192 mod 58
≡ -9 * -9 mod 58
≡ 23 mod 58
```

Some things to note:

• Substitutions with prior calculations can be made every time the exponent is squared.

For example, we already calculated 7128 mod 58 and know that it is congruent to -9 mod 58, so when we next see 7128 * 7128 mod 58 we can automatically substitute that expression for -9 * -9 mod 58 (and we can substitute even further if we wish and cut it even more intermediate calculations).

• We stop when the next squared exponent is greater than the exponent we’re calculating. In other words:

`16384 < 17684 < 32768`

Sweet. Now onto…

## Binary Expansion

The last step is to write out our large exponent in binary form, that is, to do a binary expansion:

`1768410 = 0100 0101 0001 01002`

We note that there is a 1 in the following places:

• 16384
• 1024
• 256
• 16
• 4

Substituting these for 717684, we get:

`716384+1024+256+16+4 mod 58`

That, of course, can be rewritten as:

`716384 * 71024 * 7256 * 716 * 74 mod 58`

This should now look familiar! We’ve already computed these expressions above, so let’s simply plug in the results and calculate:

```23 * -9 * 23 * -9 * 23 mod 58
233 * 81 mod 58
985527 mod 58
49 mod 58
```

Neat!

We can see that the number takes up 15 bits of storage:

`Math.ceil(Math.log2(17684))`

## Euler’s Theorem

A really nice way to reduce the large exponent is by using Euler’s theorem, but only if the base is coprime to the modulus (another way to think of it is if the greatest common divisor of both numbers is 1). In our case they are relatively prime to each other, so we’re in luck!

Recall Euler’s theorem:

`aϕ(n) ≡ 1 mod n`

Let’s get to work!

```717684 mod 58

7ϕ(58) ≡ 1 mod 58

Let's calculate ϕ(58):
ϕ(58) = 58(1 - 1/2)(1 - 1/29)*
ϕ(58) = 58(1/2)(28/29)
ϕ(58) = 28

728 ≡ 1 mod 58

Let's use the division algorithm to reduce the large exponent
(the result of the phi function will be the divisor):
n = dq + r, where 0 <= r < d
17684 = 28(631) + 16

7(28*631+16) mod 58
728631 * 716 mod 58

Recall that 728 ≡ 1 mod 58, so we can substitute:
1631 * 716 mod 58
1 * 716 mod 58
716 mod 58

An exponent of 16 is much better to compute than one of 17684!
33232930569601 mod 58
49 mod 58

* The numbers 2 and 29 are the prime factorization of 58.
```

If any of these computations seem unfamiliar, please see my articles on Euler’s theorem and coding Euler’s totient function.

## Conclusion

This is some cool shit, man.