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 7¹²⁸ mod 58 and know that it is congruent to -9 mod 58, so when we next see 7¹²⁸ * 7¹²⁸ 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 7¹⁷⁶⁸⁴, 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.