1. Reduce base
Take the base modulo m up front to keep numbers small.
base = base % modTyporithm · medium
Modular Exponentiation
▷ Interactive algorithm labmodular-exponentiationmathmod-arithmetichalvingoverflow
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Modular Exponentiation
Math & Number Theory
Square-and-multiply: fold the base in on each set exponent bit, taking the modulus after every product.
Computing base^exp directly overflows fast, so the modulus is applied throughout.
Binary exponentiation squares the base each step and multiplies it into the result on a 1 bit.
Reducing modulo m after every multiply keeps all intermediate values bounded.
Preparing algorithm lab…
01
Square the base each step.
02
Multiply in on odd exponent bits.
03
Reduce mod m after every product.
function modPow(base, exp, mod) {
let result = 1;
base = base % mod;
while (exp > 0) {
if (exp % 2 === 1) {
result = (result * base) % mod;
}
exp = Math.floor(exp / 2);
base = (base * base) % mod;
}
return result;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Odd bit
When the current exponent bit is 1, fold the base into the result.
if (exp % 2 === 1)3. Multiply mod
Apply the modulus after every multiply to prevent overflow.
result = (result * base) % mod4. Shift exponent
Move to the next exponent bit by halving.
exp = Math.floor(exp / 2)5. Square base
Square the base each step, reduced modulo m.
base = (base * base) % modA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.