Skip to content

Powers Mod M

01 · Question

Given integers a ≥ 1, p ≥ 0, and m > 1, return a^p mod m without constructing the full power. Reduce intermediate results as the computation proceeds.

Examples: a=2, p=5, m=100 → 32; a=2, p=5, m=30 → 2; a=7, p=0, m=13 → 1. Go accepts uint64 inputs.

02 · Analysis

Recurrence: let h = power(a, floor(p/2), m). For even p return h² mod m; for odd p return (h² mod m) · (a mod m) mod m. For p=0 return 1. Compute h once, not twice.

There is one recursive child per call: O(log(p+1)) modular multiplications and O(log(p+1)) stack frames, with constant work for p=0. Python first reduces a, so multiplication intermediates are below m² rather than as large as a^p; arbitrary-precision multiplication has a cost depending on the bit length of m.

For Go, ordinary uint64 multiplication can overflow before the modulo. The math/bits functions preserve the 128-bit product with Mul64 and reduce it with Div64. With both factors below m, the product's high word is below m, satisfying Div64's quotient-overflow precondition. This supports the full uint64 modulus range.

03 · Solution

Reference solution

1def power_mod(a, p, m):
2    a %= m
3    def visit(exponent):
4        if exponent == 0:
5            return 1
6        half = visit(exponent // 2)
7        result = (half * half) % m
8        if exponent % 2:
9            result = (result * a) % m
10        return result
11    return visit(p)
Previous
Nested Array Sum
Next
Lego Castle