18.6 Fast Exponentiation
Exponentiation appears constantly in number-theoretic algorithms.
18.6 Fast Exponentiation
Exponentiation appears constantly in number-theoretic algorithms. Modular arithmetic, primality testing, cryptography, polynomial hashing, matrix recurrence solving, and combinatorial counting all depend on computing powers efficiently.
The direct method is simple: multiply the base by itself repeatedly. That works for small exponents, but fails quickly when the exponent is large. Fast exponentiation, also called exponentiation by squaring, reduces the number of multiplications from linear to logarithmic.
Problem
Given:
base
exponent
modulus
compute:
base^exponent mod modulus
efficiently.
For example:
7^1000 mod 13
Computing 7^1000 directly creates an enormous intermediate integer. Instead, we want to reduce during the computation and use the binary structure of the exponent.
Naive Approach
The direct method multiplies base exactly exponent times.
def pow_naive(base, exponent, modulus):
result = 1
for _ in range(exponent):
result = (result * base) % modulus
return result
Example:
print(pow_naive(7, 10, 13))
Output:
4
This is correct, but the complexity is:
O(exponent)
For small exponents, this is acceptable. For cryptographic exponents with hundreds or thousands of bits, it is unusable.
Key Observation
The square of a power gives another power:
a^(2k) = (a^k)^2
For odd exponents:
a^(2k+1) = a × (a^k)^2
This means we can cut the exponent roughly in half at each step.
Example:
7^10 = (7^5)^2
7^5 = 7 × (7^2)^2
Instead of multiplying ten times, we repeatedly square and only multiply into the result when the current exponent bit is set.
Recursive Version
A direct recursive implementation mirrors the mathematics.
def fast_pow(base, exponent):
if exponent == 0:
return 1
half = fast_pow(base, exponent // 2)
if exponent % 2 == 0:
return half * half
return base * half * half
Example:
print(fast_pow(2, 10))
Output:
1024
This reduces the number of recursive levels to:
O(log exponent)
However, without a modulus, values can still become very large.
Modular Fast Exponentiation
For number-theoretic algorithms, we usually compute powers modulo m.
def mod_pow(base, exponent, modulus):
if modulus == 1:
return 0
base %= modulus
result = 1
while exponent > 0:
if exponent & 1:
result = (result * base) % modulus
base = (base * base) % modulus
exponent >>= 1
return result
Example:
print(mod_pow(7, 1000, 13))
Output:
9
The function never stores 7^1000. It keeps every intermediate value reduced modulo 13.
Reading the Binary Exponent
The algorithm works because every exponent has a binary representation.
Example:
13 = 1101₂
Therefore:
a^13 = a^(8+4+1)
which equals:
a^8 × a^4 × a
Fast exponentiation computes the sequence:
a, a^2, a^4, a^8, ...
by repeated squaring, then multiplies only the powers corresponding to 1 bits in the exponent.
For 13, the selected powers are:
a^1
a^4
a^8
because:
13 = 8 + 4 + 1
Step-by-Step Example
Compute:
3^13 mod 17
Binary representation:
13 = 1101₂
Initialize:
result = 1
base = 3
exponent = 13
Step 1: exponent is odd.
result = 1 × 3 mod 17 = 3
base = 3² mod 17 = 9
exponent = 6
Step 2: exponent is even.
result = 3
base = 9² mod 17 = 13
exponent = 3
Step 3: exponent is odd.
result = 3 × 13 mod 17 = 5
base = 13² mod 17 = 16
exponent = 1
Step 4: exponent is odd.
result = 5 × 16 mod 17 = 12
base = 16² mod 17 = 1
exponent = 0
Final answer:
3^13 mod 17 = 12
Why It Works
At every iteration, the algorithm maintains an invariant:
result × base^exponent
has the same value as the original power, modulo modulus.
When the exponent is odd, one factor of base is moved into result:
base^exponent = base × base^(exponent-1)
When the exponent is even, the algorithm squares the base and halves the exponent:
base^exponent = (base^2)^(exponent/2)
Both transformations preserve the invariant. When the exponent reaches zero, the remaining value is held in result.
Complexity
Each loop iteration halves the exponent.
Time complexity:
O(log exponent)
Space complexity:
O(1)
for the iterative version.
This is a major improvement over the naive algorithm:
O(exponent)
For an exponent with k bits, fast exponentiation takes O(k) iterations.
Handling Large Multiplication
The expression:
(result * base) % modulus
can overflow in languages with fixed-width integers, even when the final result fits.
Python integers grow automatically, so this is safe in Python. In C, C++, Go, Rust, Java, or similar languages, you may need one of the following:
128-bit integer multiplication
Montgomery multiplication
Barrett reduction
Repeated-doubling multiplication
Big integer libraries
For ordinary competitive programming constraints, a 64-bit modulus often requires 128-bit intermediate multiplication.
Fast Power Without Modulus
The same technique works for ordinary exponentiation.
def int_pow(base, exponent):
result = 1
while exponent > 0:
if exponent & 1:
result *= base
base *= base
exponent >>= 1
return result
This still has logarithmic multiplication count, but the numbers themselves may grow exponentially in size. For large exponents, the cost of big-integer multiplication becomes significant.
Matrix Exponentiation
Fast exponentiation applies to any associative operation.
For example, it can be used with matrices.
def mat_mul(A, B):
return [
[
A[0][0] * B[0][0] + A[0][1] * B[1][0],
A[0][0] * B[0][1] + A[0][1] * B[1][1],
],
[
A[1][0] * B[0][0] + A[1][1] * B[1][0],
A[1][0] * B[0][1] + A[1][1] * B[1][1],
],
]
def mat_pow(matrix, exponent):
result = [
[1, 0],
[0, 1],
]
while exponent > 0:
if exponent & 1:
result = mat_mul(result, matrix)
matrix = mat_mul(matrix, matrix)
exponent >>= 1
return result
This is commonly used to compute linear recurrences such as Fibonacci numbers in logarithmic time.
Fibonacci Example
The Fibonacci sequence can be represented by a matrix:
[ F(n+1) ] [ 1 1 ]^n [ 1 ]
[ F(n) ] = [ 1 0 ] [ 0 ]
Using matrix exponentiation, F(n) can be computed in:
O(log n)
matrix multiplications.
This pattern generalizes to many recurrence relations.
Modular Exponentiation in Cryptography
RSA encryption and decryption both use modular exponentiation.
A typical operation looks like:
c = m^e mod n
and:
m = c^d mod n
The exponents e and d may be very large. Without fast exponentiation, RSA would be computationally impractical.
The same technique appears in Diffie-Hellman key exchange, digital signatures, primality testing, and finite-field arithmetic.
Common Mistakes
Computing the Full Power First
Avoid this:
answer = (base ** exponent) % modulus
For small numbers it is fine. For large exponents, it creates huge intermediate values.
Use modular exponentiation instead.
Forgetting to Reduce the Base
Always begin with:
base %= modulus
This keeps intermediate values smaller.
Mishandling Exponent Zero
For any nonzero modulus:
a^0 mod m = 1 mod m
So the initial result should be:
1
Ignoring Modulus One
When:
modulus = 1
every integer is congruent to zero. Return 0.
Overflow Before Reduction
In fixed-width integer languages, multiplication can overflow before % is applied. Use a wider integer type or a safe modular multiplication method.
Testing
Basic test cases:
def test_mod_pow():
assert mod_pow(2, 0, 5) == 1
assert mod_pow(2, 10, 1000) == 24
assert mod_pow(3, 13, 17) == 12
assert mod_pow(7, 1000, 13) == 9
assert mod_pow(10, 5, 1) == 0
A useful property test compares against Python's built-in pow:
def test_against_builtin():
for base in range(1, 50):
for exponent in range(0, 50):
for modulus in range(1, 50):
assert mod_pow(base, exponent, modulus) == pow(base, exponent, modulus)
This style of test is especially effective because modular exponentiation has many boundary cases.
Takeaway
Fast exponentiation replaces repeated multiplication with repeated squaring. The algorithm uses the binary representation of the exponent, multiplies into the result only when a bit is set, and reduces intermediate values modulo m. This reduces the running time from O(exponent) to O(log exponent) and makes large-scale modular arithmetic practical. It is a core subroutine for modular inverses, primality testing, RSA, Diffie-Hellman, polynomial algorithms, matrix recurrences, and many other number-theoretic algorithms.