Fast Modular Exponentiation
What this concept is
Repeated squaring computes a^e mod m for nonnegative e and positive m without constructing the enormous full power. Keep an accumulator, a reduced base and a remaining exponent. Multiplying two congruent representatives preserves the final residue.
Why it matters here
This connects a mathematical identity to an efficient loop and prepares binary decomposition and invariant reasoning for algorithms.
Concrete example
For 3^13 mod 17, the powers 3^1,3^2,3^4,3^8 have residues 3,9,13,16. Since 13=8+4+1, multiply 16133 and reduce to get 12.
An iterative algorithm initializes result=1 % m, base=a % m, remaining=e. If remaining is odd, multiply result by base modulo m; square base modulo m; halve remaining with integer division. Repeat until remaining is zero.
Invariant: result * base^remaining ≡ original_a^original_e (mod m). For even remaining, squaring and halving preserve the expression. For odd remaining, first move one factor into result, then square and halve. At termination the remaining exponent is zero, leaving the desired result.
Common confusion / misconception
Exponent zero requires 1 % m, which is 0 when m=1. Our API defines this result even for a=0; it is a deliberate computational convention. Negative exponents are rejected in this lab rather than implicitly requesting an inverse. Python ^ is not exponentiation.
How to use it
Trace the accumulator, base and exponent before each iteration. There are logarithmically many iterations for positive e, but multiplication/reduction cost depends on operand size. A short loop is not by itself a constant-time cryptographic algorithm.
Check yourself
What should power_mod(-2,3,5), power_mod(9,0,7) and power_mod(0,0,1) return? Answers: 2,1,0 under the stated contract.
Mini drill or application
Compute 5^11 mod 13 using squared residues and verify with an independent oracle after your hand trace. Write down why an ordinary power-then-remainder approach does much more intermediate work.
Read this only if stuck
Source backbone: Mathematics for Computer Science reference. For the freely available original, use MIT’s 2015 Chapter 8 readings. See the reading guide for topic selection; chapter numbering can differ across editions.