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:

3^{5 * 7}= 3^{57}3^{5 + 7}= 3^{5}* 3^{7}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!).

3^{76}mod 11 1. Reduce using exponentiation by squaring. 3^{1}mod 11 ≡ 3 mod 11 3^{2}mod 11 ≡ 9 mod 11 3^{4}mod 11 ≡ 3^{2+2}mod 11 ≡ 3^{2}* 3^{2}mod 11 ≡ 9 * 9 mod 11 ≡ 81 mod 11 ≡ 4 mod 11 3^{8}mod 11 ≡ 3^{4+4}mod 11 ≡ 3^{4}* 3^{4}mod 11 ≡ 4 * 4 mod 11 <--- We substitute here using the result of 3^{4}≡ 16 mod 11 ≡ 5 mod 11 3^{16}mod 11 ≡ 3^{8+8}mod 11 ≡ 5 * 5 mod 11 ≡ 25 mod 11 <--- Substitute! ≡ 3 mod 11 3^{32}mod 11 ≡ 3^{16+16}mod 11 ≡ 3 * 3 mod 11 <--- Substitute! ≡ 9 mod 11 3^{64}mod 11 ≡ 3^{32+32}mod 11 ≡ 4 mod 11 <--- Substitute! - Do the binary expansion of the base_{10}exponent - and write the exponent anew, substituting in - the power of 2s where the bit is 1. 76_{10}= 0100 1100_{2}3^{64+8+4}mod 11 3^{64}* 3^{8}* 3^{4}mod 11 - Substitute and calculate! 4 * 5 * 4 mod 11 80 mod 113mod 11 2. Reduce by Euler's theorem. 3^{ϕ(11)}≡ 1 mod 11 3^{10}≡ 1 mod 11 3^{10*7+6}mod 11 3^{107}* 3^{6}mod 11 1^{7}* 3^{6}mod 11 729 mod 113mod 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`

:

`7`

^{17684} 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!

7^{1}mod 58 ≡ 7 mod 58 7^{2}mod 58 ≡ 49 mod 58 7^{4}mod 58 ≡ 7^{2+2}mod 58 ≡ 7^{2}* 7^{2}mod 58 ≡ 49 * 49 mod 58 ≡ 2401 mod 58 ≡ 23 mod 58 7^{8}mod 58 ≡ 7^{4+4}mod 58 ≡ 7^{4}* 7^{4}mod 58 ≡ 23 * 23 mod 58 ≡ 529 mod 58 ≡ 7 mod 58 7^{16}mod 58 ≡ 7^{8+8}mod 58 ≡ 7^{8}* 7^{8}mod 58 ≡ 7 * 7 mod 58 ≡ 49 mod 58 ≡ -9 mod 58 7^{32}mod 58 ≡ 7^{16+16}mod 58 ≡ 7^{16}* 7^{16}mod 58 ≡ -9 * -9 mod 58 ≡ 81 mod 58 ≡ 23 mod 58 7^{64}mod 58 ≡ 7^{32+32}mod 58 ≡ 7^{32}* 7^{32}mod 58 ≡ 23 * 23 mod 58 ≡ 529 mod 58 ≡ 7 mod 58 7^{128}mod 58 ≡ 7^{64+64}mod 58 ≡ 7^{64}* 7^{64}mod 58 ≡ 7 * 7 mod 58 ≡ -9 mod 58 7^{256}mod 58 ≡ 7^{128+128}mod 58 ≡ -9 * -9 mod 58 ≡ 81 mod 58 ≡ 23 mod 58 7^{512}mod 58 ≡ 7^{256+256}mod 58 ≡ 23 * 23 mod 58 ≡ 7 mod 58 7^{1024}mod 58 ≡ 7^{512+512}mod 58 ≡ 7 * 7 mod 58 ≡ -9 mod 58 7^{2048}mod 58 ≡ 7^{1024+1024}mod 58 ≡ -9 * -9 mod 58 ≡ 23 mod 58 7^{4096}mod 58 ≡ 7^{2048+2048}mod 58 ≡ 23 * 23 mod 58 ≡ 7 mod 58 7^{8192}mod 58 ≡ 7^{4096+4096}mod 58 ≡ 7 * 7 mod 58 ≡ -9 mod 58 7^{16384}mod 58 ≡ 7^{8192+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

^{128}mod 58 and know that it is congruent to -9 mod 58, so when we next see 7^{128}* 7^{128}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:

`17684`

_{10} = 0100 0101 0001 0100_{2}

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

- 16384
- 1024
- 256
- 16
- 4

Substituting these for 7^{17684}, we get:

`7`

^{16384+1024+256+16+4} mod 58

That, of course, can be rewritten as:

`7`

^{16384} * 7^{1024} * 7^{256} * 7^{16} * 7^{4} 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 23^{3}* 81 mod 58 985527 mod 5849mod 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!

7^{17684}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 7^{28}≡ 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 7^{28631}* 7^{16}mod 58 Recall that 7^{28}≡ 1 mod 58, so we can substitute: 1^{631}* 7^{16}mod 58 1 * 7^{16}mod 58 7^{16}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.