Fast exponentiation algorithm to evaluate 3^(2^(n))

Question

Carry out the fast exponentiation algorithm to evaluate 3^(2^(n)) mod 13 for n = 0, 1 and 2. These three values suffice to derive a formula for 3^(2^(n)) mod 13 for all non-negative integers n. State this formula and explain.

How do I go about this, and how do you apply the fast exponentiation algorithm to an exponent of an exponent?

Answer 1

Fast exponentiation works especially well when the exponent is of the form 2^k. But rather than wonder about why, let's just do the first three examples, then see if we can see the pattern enough to generalize. I should add that the fast exponentiation algorithm has multiple equivalent ways of being described, so it's possible I may do things in a way that looks different than how it was introduced to you. Rest assured it's really the same algorithm, but feel free to follow up in a comment if anything is unclear.

The way I'm going to do the algorithm is this: x gets initialized as our base, n gets initialized as our exponent. We also begin by writing n in binary. r gets initialized as 1; this is what we will be using to eventually compute the exponent modulo 13. Before every step, we will square r and take its residue modulo 13. Then at each step we read the binary representation of n. If the next digit is a 1, multiply r by x. If the next digit is a zero, do nothing.

First, x=3, n=2⁰. We wish to compute 3¹ mod 13. Initialize r=1. Square r² = 1*1 = 1. Our exponent 2⁰ is just 1 in binary. Multiply r*x = 3. So 3¹ ≡ 3 mod 13.

Next, x=3, n=2¹. We wish to compute 3² mod 13. Initialize r=1. Square r² = 1*1 = 1. Our exponent 2¹ is just 10 in binary. The first bit is a 1, so r becomes r*x = 3. Square r² = 3*3 = 9. The second bit is a zero, so we are done. So 3² ≡ 9 mod 13.

Next, x=3, n=2². We wish to compute 3⁴ mod 13. Initialize r=1. Square r² = 1*1 = 1. Our exponent 2² is 100 in binary. The first bit is a 1, so r becomes r*x = 3. Square r² = 3*3 = 9. The second bit is a zero, so no need to multiply by x. Square r² = 9*9 = 81, which equals 3 mod 13. The third bit is a zero, so still no need to multiply by x. We are done: 3⁴ ≡ 3 mod 13.

What did we learn from all of this? When fast exponentiating, if our exponent is itself a power of 2, then its binary expansion will be a 1 followed by some zeros. Which means the fast exponentiation algorithm will just have us initiate by multiplying by the base once, then squaring a number of times, reducing mod 13 after each squaring.

We saw the results of the first few squarings: we went 3 --> 9 --> 3. But 3² is still 9 so this pattern will repeat for larger powers of 2 in the exponent. We will have 3 --> 9 --> 3 --> 9 --> ...

In fact, the pattern is that 3^{(2^k)} ≡ 3 when k is even and ≡ 9 when k is odd.