Fast Modular Exponentiation
Compute powers with pow(a, b, m).
The Power Problem
You often need a number raised to a giant exponent, all under a modulus. Multiplying one factor at a time would take far too many steps. ⚡
Naive Is Too Slow
A loop multiplying b times runs in O(b) steps. With an exponent near a billion, that blows past the time limit before it ever finishes.
for _ in range(b): r = r * a % MODAll lessons in this course
- Work Modulo a Prime
- Fast Modular Exponentiation
- Modular Inverse via Fermat
- nCr with Precomputed Factorials