Compute Modular Power

Practice Exercise Intermediate Medium Array Modular Arithmetic

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement modular_power(base, exponent, modulus). exponent is nonnegative and modulus is positive. Do not use pow with three arguments or **.

Starter code

def modular_power(base, exponent, modulus):
    pass

Test cases

large-power

{
  "args": [
    7,
    128,
    13
  ]
}

Expected: 3

zero-exponent

{
  "args": [
    5,
    0,
    1
  ]
}

Expected: 0

Wizard outline

Step 1: Establish the exponent-zero identity
Return the modular multiplicative identity for exponent zero. Any nonzero base to exponent zero is one before modular reduction.
Step 2: Accumulate repeated modular products
Handle exponent three one factor at a time. Reducing after each multiplication preserves the final modular result.
Step 3: Replace linear multiplication with squaring
Consume exponent bits and square the base each round. Binary exponentiation combines powers selected by set bits in logarithmic rounds.

Footguns and prerequisites

Computing base**exponent first defeats the bounded-intermediate-value goal.
For exponent zero the result is 1 % modulus, not always 1.
functions
lists and tuples
control flow

Reviewed references

Python More on Lists

Recommended approach and implementation

Use binary exponentiation while reducing every multiplication modulo modulus.

Why it works: At each iteration, result times base raised to the remaining exponent is congruent to the original power. Consuming odd bits and squaring preserves this invariant until exponent reaches zero.

def modular_power(base, exponent, modulus):
    result = 1 % modulus
    base %= modulus
    while exponent > 0:
        if exponent & 1:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent //= 2
    return result