Chapter 6: Where All Roads Meet: Modular Exponentiation

Team-Fly

---

Overview

Two roads diverged in a yellow wood,

And sorry I could not travel both

And be one traveler, long I stood ...

—Robert Frost, "The Road Not Taken"

IN ADDITION TO THE CALCULATIONAL rules for addition, subtraction, and multiplication in residue classes we can also define an operation of exponentiation, where the exponent specifies how many times the base is to be multiplied by itself. Exponentiation is carried out, as usual, by means of recursive calls to multiplication: For a in we have a⁰ := and a^e+1 := a · a^e.

It is easy to see that for exponentiation in the usual rules apply (cf. Chapter 1):

---

Team-Fly