DSA Fast Power and Modular Arithmetic

Fast power is a method that raises a base to a large exponent by repeated squaring. A modular remainder keeps every intermediate value below a fixed bound.

Squaring beats step by step

A plain loop for 3 to the 13th power multiplies 12 times. Squaring follows the binary digits of 13 instead.

steps = 0
result = 3
for _ in range(12):
    result *= 3
    steps += 1
print("plain loop answer:", result, "multiplications:", steps)
print("13 in binary:", format(13, "b"))

Remainders keep values small

Without a modulus the power grows to 17 digits in this small case. With a remainder after each step the value stays below the modulus.

big = 7 ** 20
print("7 to the 20th:", big)
print("digits:", len(str(big)))
value = 1
for _ in range(20):
    value = (value * 7) % 5
print("7 to the 20th mod 5:", value)
print("built-in check:", pow(7, 20, 5))

Read the exponent in binary

The exponent 10 is 1010 in binary, so two squared values multiply in. The squares are 2, 4, 16 and 256.

squares = []
value = 2
for _ in range(4):
    squares.append(value)
    value = value * value
print("squares of 2:", squares)
print("2 to the 10th from squares:", squares[1] * squares[3])

Example

def fast_power_mod(base, exp, mod):
    steps = 0
    result = 1 % mod
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
            steps += 1
        base = (base * base) % mod
        steps += 1
        exp = exp >> 1
    return result, steps

cases = [(2, 100, 1000), (3, 50, 97), (123, 45, 100000), (7, 1000, 13)]
for base, exp, mod in cases:
    value, steps = fast_power_mod(base, exp, mod)
    print(base, "to the", exp, "mod", mod, "=", value, "| multiplications:", steps, "| matches built-in:", value == pow(base, exp, mod))

Key points

Fast power raises a base to an exponent by repeated squaring.
Squaring means multiplying a value by itself.
The binary form of the exponent selects which squared values get multiplied in.
A modular remainder is the remainder of a value after division by the modulus.
Taking the remainder after each multiplication keeps the answer unchanged.
The remainder rule holds because extra full turns of the modulus add nothing.
Each halving of the exponent adds at most two multiplications.

In this example, each case runs the squaring loop with a counter. The counter rises once per multiplication the loop performs. The binary length of the exponent caps how many steps can run. A plain loop would need one multiplication per exponent step. The last column checks every answer against the built-in modular power.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

def fast_power_mod(base, exp, mod):
    steps = 0
    result = 1 % mod
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
            steps += 1
        base = (base * base) % mod
        steps += 1
        exp = exp >> 1
    return result, steps

cases = [(2, 100, 1000), (3, 50, 97), (123, 45, 100000), (7, 1000, 13)]
for base, exp, mod in cases:
    value, steps = fast_power_mod(base, exp, mod)
    print(base, "to the", exp, "mod", mod, "=", value, "| multiplications:", steps, "| matches built-in:", value == pow(base, exp, mod))

Exercise

How many squarings can an exponent below 64 need at most?

64 32 63 6