Modular exponentiation is a very important building block of modern cryptography, which is the way our messages and traffic are encrypted and kept secure and private as they are transported across the internet.
Recall: The modulus operation is closely related to division. The modulus is just another way of saying the remainder that’s left over after a number is divided evenly as many times as possible. As an illuminating example, consider 7 divided by 3. 3 goes into 7 evenly twice, with a remainder of 1 left over. In this case, 7 (mod 3) is equal to 1.
We are familiar with normal exponents from math class, such as 75, in which 7 is multiplied by itself 5 times to get the result 16807. Many key modern encryption techniques rely on performing the operation be (mod m) where b and e are both very large numbers that you take the modulus of in the end. In practice, b and e may be both so large that actually performing the exponentiation operation and then taking the modulus would make the process too slow. Instead, we can use a trick to make the result much more practical to compute.
It turns out that from the rules of modulus, be (mod m) is equivalent to (b mod m)e (mod m). To look at this more concretely:
75 (mod 3) = (7 mod 3)5 (mod 3) = (1)5 (mod 3) = 1
The practical benefit of this can be seen when we consider larger values of b, e, and m. Consider b = 255, e=5, and m = 457, so that we wish to find 2555 (mod 457). Then:
2555 (mod 457) =
(2554 (mod 457)) * (255) (mod 457) =
(2553 (mod 457)) * (255 * 255 (mod 457)) (mod 457) = (2553 (mod 457)) * 131 (mod 457) =
(2552 (mod 457)) * (131 * 255 (mod 457)) (mod 457) = (2552 (mod 457)) * 44 (mod 457) =
(2551 (mod 457)) * (44 * 255 (mod 457)) (mod 457) = (2551 (mod 457)) * 252 (mod 457) =
255 * 252 (mod 457) = 280
From this, we can see that the numbers we are multiplying at any given step are always lower than the modulus number, in this case, 457.
Challenge: Write a program that reads in a base, an exponent, and a modulus performs modular exponentiation on them, and prints the result. Do not use any built in exponent or modular exponentiation code from your target language, try and write it from hand! You will not need any advanced math or code knowledge other than the rules explained above, the modulus operator (which is % in both Java and Python), and your programming fundamentals through for loops!
