The typical approach to exponentiation of a base b by an exponent n is to repeatedly multiply the base by itself, as such:
This is easy to compute for small values but quickly chokes with very large values.
A faster approach involves converting the exponent into base 2, then multiplying the running total and squaring the base each time a 1-bit is encountered. The python implementation looks like this:
def binary_exponent(base, exponent): """\ Binary Exponentiation Instead of computing the exponentiation in the traditional way, convert the exponent to its reverse binary representation. Each time a 1-bit is encountered, we multiply the running total by the base, then square the base. """ # Convert n to base 2, then reverse it. exponent = bin(exponent)[2:][::-1] result = 1 for i in range(0, len(exponent)): if exponent[i] == '1': result *= base base *= base return result |
Similarly, the same approach can be taken to perform modular exponentiation against very large exponents:
def modular_exponent(base, exponent, mod): """\ Modular exponentiation through binary decomposition. We use the same technique as for the binary exponentiation above in order to find the modulo of our very large exponent and an arbitrary integer mod. """ exponent = bin(exponent)[2:][::-1] x = 1 power = base % mod for i in range(0, len(exponent)): if exponent[i] == '1': x = (x * power) % mod power = (power ** 2) % mod return x |
The optimization is especially visible for the modulo operation, since we are working on smaller numbers with each iteration, whereas for simple exponentiation, the CPython interpreter can already optimize the operation.
The speedup for modular exponentiation on my system was in the order of 72x the speed of a simple 
Related posts: