Power Mod: Modular Exponentiation

Why the Modular Exponentiation?

Modular Exponentiation has applications in the field of Cryptography and is used to reduce the time complexity of multiplication operations, which can be expensive, and utilize very large numbers. Modular Exponentiation reduces the number of bits that the multiplicand uses, thus reducing the time complexity for large powers.

For example \(100 \times 100 = 10000\) where \(100\) is represented by 8 bits, and \(10000\) is represented by 16 bits.

So at most the multiplicand's number of bits would remain in the \(\#bits \leq log_2{m}\) where \(m\) is the number we are performing the modulus by.

Algorithm

# Pseudo Code
def powermod(x, e, m):
	if e == 0 return 1
	if e == 1 return x

	f = e/2   # Integer Arithmetic
	y = powermod(x, f, m)
	y = (y * y) % m
	if e is odd:
		y = (y * x) % m
	return y

Additional References

Primes, Modular Arithmetic, and Public Key Cryptography
Wikipedia - Modular Exponentiation
Wikipedia - Modular Arithmetic