Fast Modular Exponentiation
Compute powers with pow(a, b, m).
Fast Modular Exponentiation is a free Coding Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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 % MODSquare to Climb Faster
The trick is squaring: a to the 8th equals ((a squared) squared) squared. Each squaring doubles the exponent, so you reach huge powers in few steps.
Read the Exponent in Binary
Every exponent is a sum of powers of two, its binary form. So you only multiply in the base powers where a bit is set, skipping the rest.
# 13 = 1101 -> a^8 * a^4 * a^1Check the Lowest Bit
Look at b & 1 to test the lowest bit. If it is 1, fold the current base into your running result before moving on.
if b & 1: result = result * base % MODShift and Square Each Round
After each bit, square the base and shift the exponent right by one. The loop runs only about 30 to 60 times for any realistic input.
base = base * base % MOD
b >>= 1Putting It Together
Start result at 1, then loop while the exponent is positive. This whole fast exponentiation idea is also called binary or exponentiation by squaring.
result = 1
while b > 0:
if b & 1: result = result*base%MOD
base = base*base%MOD
b >>= 1It Runs in Log Time
Because each round halves the exponent, the cost is O(log b). That turns a billion multiplications into roughly thirty, well within any limit.
Python Hands You pow
You rarely write the loop yourself: Python's built-in pow(a, b, m) does fast modular exponentiation for you in pure C speed.
print(pow(2, 100, MOD))Why It Matters Soon
Fast power is the engine behind the modular inverse by Fermat, which you will meet next. Master it now and division under a mod becomes easy.
Watch the Base First
Reduce the base with base % MOD before the loop. A base already larger than the modulus would otherwise inflate every squaring step.
base = a % MODQuick Check
How fast is fast modular exponentiation?
Recap
You can now raise numbers to massive exponents in O(log b) by squaring and reading bits. In Python, just call pow(a, b, m) and move on. 🚀
Frequently asked questions
Is the “Fast Modular Exponentiation” lesson free?
Yes — the full text of “Fast Modular Exponentiation” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Fast Modular Exponentiation”?
Compute powers with pow(a, b, m). You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Fast Modular Exponentiation” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Work Modulo a Prime
- Fast Modular Exponentiation
- Modular Inverse via Fermat
- nCr with Precomputed Factorials