15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Binary exponentiation computes a^b by reading the bits of b. While the exponent is positive, multiply the result by the current base if the exponent is odd, then square the base and halve the exponent. It needs O(log b) multiplications instead of b, and reducing mod m after each step gives modular exponentiation.
| Time | O(log b) for exponent b; the loop halves b each pass |
|---|---|
| Extra space | O(1): result, base and exponent |
| Identities | a^(2k) = (a²)^k and a^(2k+1) = a × (a²)^k |
| Invariant | result × base^exponent equals a^b, mod m in the modular version |
| Inputs | exponent >= 0, modulus > 0; a^0 = 1 and 0^0 = 1 by this convention |
| Modulus 1 | Every result is 0, so 5^0 mod 1 = 0 |
This lesson assumes you can read the binary form of a nonnegative integer and recognize whether its lowest bit is 0 or 1.
We will compute powers with nonnegative integer exponents.
When an exponent is even, square the base and halve the exponent. When an exponent is odd, move one copy of the current base into the answer, then apply the even-exponent step.
For modular exponentiation, compute:
where:
b >= 0m > 0After every multiplication, reduce modulo m. result and base then remain congruent to their unreduced values modulo m.
A negative exponent is outside this algorithm's input contract.
Repeated squaring processes the exponent one binary bit at a time. Reference: Binary exponentiation.
Compute:
Write the exponent in binary:
So:
The 1 bits of 1101₂ select the powers , , and . The 0 bit does not select .
Keep three state variables:
| Variable | Meaning at the start |
|---|---|
result | The selected powers multiplied so far |
base | The current power of the original base |
exponent | The portion of the exponent not processed yet |
Start here:
| result | base | exponent |
|---|---|---|
| 1 | 3 | 13 |
The exponent is odd. Its lowest binary bit is 1, so the current base, which is 3, belongs in result.
Use modular arithmetic throughout this example. Reduce every multiplication result modulo .
Square the base each round and halve the exponent; multiply base into result when the exponent is odd. For 3^13 mod 17 the state ends at result = 12 with exponent 0.
| result | base | exponent | exponent odd? |
|---|---|---|---|
| 1 | 3 | 13 | yes |
Because exponent is odd:
Now square the base and halve the exponent:
New state:
| result | base | exponent |
|---|---|---|
| 3 | 9 | 6 |
| result | base | exponent | exponent odd? |
|---|---|---|---|
| 3 | 9 | 6 | no |
The exponent is even, so result does not change.
Square the base and halve the exponent:
New state:
| result | base | exponent |
|---|---|---|
| 3 | 13 | 3 |
| result | base | exponent | exponent odd? |
|---|---|---|---|
| 3 | 13 | 3 | yes |
The exponent is odd, so multiply result by base:
Then square the base and halve the exponent:
New state:
| result | base | exponent |
|---|---|---|
| 5 | 16 | 1 |
| result | base | exponent | exponent odd? |
|---|---|---|---|
| 5 | 16 | 1 | yes |
The exponent is odd:
Square the base and halve the exponent:
New state:
| result | base | exponent |
|---|---|---|
| 12 | 1 | 0 |
Now exponent is 0, so stop. The answer is:
Look at the starting state:
After the first iteration, the state is:
The represented value is:
Since ,
The variables still represent the original power together.
The loop invariant is:
> equals the original $a^b$. > In the modular version, the two values are congruent modulo $m$. For the example, the invariant appears in these forms: | result | base | exponent | Represented value | |---:|---:|---:|---| | 1 | 3 | 13 | $1 \times 3^{13}$ | | 3 | 9 | 6 | $3 \times 9^6$ | | 3 | 13 | 3 | $3 \times 13^3$ | | 5 | 16 | 1 | $5 \times 16^1$ | | 12 | 1 | 0 | $12 \times 1^0 = 12$ | In the modular version, each row is congruent to $3^{13}$ modulo $17$. ## Derive the Algorithm Suppose the current state satisfies:At the start of every loop iteration,
result \times base^{exponent}
and `exponent` is positive. ### When the exponent is odd Write the exponent as:exponent = 2k + 1
(result \times base) \times (base^2)^k
Use these updates: 1. Move one `base` factor into `result`. 2. Square `base` and replace `exponent` with `k`, which is $\lfloor exponent / 2 \rfloor$. ### When the exponent is even Write the exponent as:exponent = 2k
result \times (base^2)^k
`result` stays unchanged. Square `base` and halve `exponent`. Every loop iteration ends with these updates: 1. If the exponent is odd, multiply `result` by `base`. 2. Square `base`. 3. Replace `exponent` with $\lfloor exponent / 2 \rfloor$. For modular exponentiation, reduce the products modulo `modulus`. For ordinary, non-modular exponentiation, use the same state changes and omit the modulo reductions. ## Pseudocode `canonicalMod(value, modulus)` is a helper with this contract: - **Input:** integer `value`, integer `modulus > 0` - **Return:** the unique integer `r` such that $0 \le r < modulus$ and $r$ is congruent to `value` modulo `modulus` - **Mutation:** does not mutate its inputs `powMod` uses local variables only. It does not mutate `base`, `exponent`, or `modulus`. ```text 1 function powMod(base, exponent, modulus): 2 # Inputs: integer base, integer exponent >= 0, integer modulus > 0 3 # Returns: canonical value of base^exponent modulo modulus 4 # Mutation: does not mutate any input 5 6 result ← canonicalMod(1, modulus) 7 currentBase ← canonicalMod(base, modulus) 8 currentExponent ← exponent 9 10 while currentExponent > 0: 11 if currentExponent mod 2 = 1: 12 result ← canonicalMod(result × currentBase, modulus) 13 14 currentBase ← canonicalMod(currentBase × currentBase, modulus) 15 currentExponent ← floor(currentExponent / 2) 16 17 return result ``` For non-modular exponentiation, the same structure computes $a^b$: ```text function powNonnegative(base, exponent): # Inputs: integer base, integer exponent >= 0 # Returns: base^exponent # Mutation: does not mutate either input result ← 1 currentBase ← base currentExponent ← exponent while currentExponent > 0: if currentExponent mod 2 = 1: result ← result × currentBase currentBase ← currentBase × currentBase currentExponent ← floor(currentExponent / 2) return result ``` Both functions use the convention $0^0 = 1$, because `result` begins as `1` and the loop does not run when the exponent is `0`. ## Dry Run Against the Pseudocode Call: ```text powMod(3, 13, 17) ``` ### Initialization - Line 6: `result ← canonicalMod(1, 17) = 1` - Line 7: `currentBase ← canonicalMod(3, 17) = 3` - Line 8: `currentExponent ← 13` State: | result | currentBase | currentExponent | |---:|---:|---:| | 1 | 3 | 13 | ### First loop iteration - Line 10: `13 > 0`, enter the loop. - Line 11: `13 mod 2 = 1`, so enter the `if`. - Line 12: `result ← canonicalMod(1 × 3, 17) = 3` - Line 14: `currentBase ← canonicalMod(3 × 3, 17) = 9` - Line 15: `currentExponent ← floor(13 / 2) = 6` State: | result | currentBase | currentExponent | |---:|---:|---:| | 3 | 9 | 6 | ### Second loop iteration - Line 10: `6 > 0`, enter the loop. - Line 11: `6 mod 2 = 0`, skip line 12. - Line 14: `currentBase ← canonicalMod(9 × 9, 17) = 13` - Line 15: `currentExponent ← floor(6 / 2) = 3` State: | result | currentBase | currentExponent | |---:|---:|---:| | 3 | 13 | 3 | ### Third loop iteration - Line 10: `3 > 0`, enter the loop. - Line 11: `3 mod 2 = 1`, so enter the `if`. - Line 12: `result ← canonicalMod(3 × 13, 17) = 5` - Line 14: `currentBase ← canonicalMod(13 × 13, 17) = 16` - Line 15: `currentExponent ← floor(3 / 2) = 1` State: | result | currentBase | currentExponent | |---:|---:|---:| | 5 | 16 | 1 | ### Fourth loop iteration - Line 10: `1 > 0`, enter the loop. - Line 11: `1 mod 2 = 1`, so enter the `if`. - Line 12: `result ← canonicalMod(5 × 16, 17) = 12` - Line 14: `currentBase ← canonicalMod(16 × 16, 17) = 1` - Line 15: `currentExponent ← floor(1 / 2) = 0` State: | result | currentBase | currentExponent | |---:|---:|---:| | 12 | 1 | 0 | ### Stop and return - Line 10: `0 > 0` is false. Exit the loop. - Line 17: return `12`. The function returns: ```text 12 ``` ## Why the Algorithm Is Correct We prove that `powMod(base, exponent, modulus)` returns the canonical value of $base^{exponent} \bmod modulus$, for `exponent >= 0` and `modulus > 0`. ### Initialization Before the loop:result = 1 \bmod m
currentBase = base \bmod m
currentExponent = exponent
result \times currentBase^{currentExponent} \equiv 1 \times base^{exponent} \equiv base^{exponent} \pmod m
So the invariant is true before the first iteration. ### Preservation when the exponent is odd Suppose the invariant is true at the start of an iteration, and:currentExponent = 2k + 1
result \times currentBase \pmod m
currentBase^2,\quad k
(result \times currentBase) \times (currentBase^2)^k
= result \times currentBase^{2k+1}
The represented power remains unchanged. Reducing the multiplication result modulo `modulus` preserves congruence modulo `modulus`. ### Preservation when the exponent is even Suppose:currentExponent = 2k
currentBase^2,\quad k
result \times currentBase^{2k}
The represented power remains unchanged. Modular reduction preserves the same congruence class. Every loop iteration preserves the invariant. ### Termination When `currentExponent > 0`, line 15 replaces it with:\left\lfloor \frac{currentExponent}{2} \right\rfloor
currentExponent = 0
result \times currentBase^0 \equiv base^{exponent} \pmod m
Since $currentBase^0 = 1$:result \equiv base^{exponent} \pmod m
Line 6 and every later modular update keep `result` canonically normalized. The returned `result` is the canonical value of $base^{exponent} \bmod modulus$. ## Time and Space from the Work Focus on `currentExponent`. Each loop iteration replaces a positive value $e$ with:\left\lfloor \frac{e}{2} \right\rfloor
Starting from a positive exponent $b$, we can halve it at most:\lfloor \log_2 b \rfloor + 1
times before it becomes `0`. In each iteration, the algorithm performs: - one parity check, - at most one multiplication for `result`, - one multiplication to square `currentBase`, - modular reductions in the modular version, - assignments, - one division by `2` using floor. That is a constant number of operations per iteration. For $b > 0$, binary exponentiation takes:O(\log b)
time. When $b = 0$, the loop performs zero iterations and returns immediately. The algorithm stores only: - `result`, - `currentBase`, - `currentExponent`. So it uses:O(1)
auxiliary space, excluding the size of arbitrary-precision integer values. ## Where Implementations Break ### Decrementing instead of halving Incorrect update: ```text currentExponent ← currentExponent - 1 ``` Exposing input: ```text 2^1,000,000 ``` This update can still produce the correct result, but it performs one iteration per exponent unit. Its running time becomes linear in the exponent rather than logarithmic. Correction: ```text currentBase ← currentBase × currentBase currentExponent ← floor(currentExponent / 2) ``` Consume the exponent by binary digits rather than one unit at a time. ### Squaring before handling an odd exponent Incorrect order: ```text currentBase ← currentBase × currentBase currentExponent ← floor(currentExponent / 2) if currentExponent mod 2 = 1: result ← result × currentBase ``` Exposing input: ```text 3^1 ``` Wrong state after squaring and halving: | result | currentBase | currentExponent | |---:|---:|---:| | 1 | 9 | 0 | The algorithm returns `1`, but:3^1 = 3
Correction: test whether the current exponent is odd and multiply `result` by the current `base` before squaring and halving. ### Initializing `result` to zero Incorrect initialization: ```text result ← 0 ``` Exposing input: ```text 7^0 ``` The loop does not run, so this version returns `0`. The required result is:7^0 = 1
Correction: ```text result ← 1 ``` For modular exponentiation, use: ```text result ← canonicalMod(1, modulus) ``` For `modulus = 1`, the canonical result is `0`. ### Waiting until the end to reduce modulo the modulus Incorrect assumption: ```text # Compute all products first, reduce only after the loop. ``` Exposing input: ```text a large base and exponent with a small modulus ``` In a bounded-integer language, intermediate products can overflow before the final reduction. The resulting output can be corrupted even if the final mathematical value modulo `m` is small. Correction: ```text result ← canonicalMod(result × currentBase, modulus) currentBase ← canonicalMod(currentBase × currentBase, modulus) ``` Reducing after each multiplication keeps the state congruent to the intended values. An implementation must also ensure that each multiplication itself is represented safely for its chosen integer type. ### Boundary inputs to define explicitly | Input | Required result | |---|---:| | $2^0$ | $1$ | | $0^5$ | $0$ | | $0^0$ | $1$, using this lesson’s algorithmic convention | | $5^0 \bmod 7$ | $1$ | | $5^0 \bmod 1$ | $0$ after canonical modular normalization | A negative exponent is not accepted by this integer algorithm. ## Practice Implement: ```text powMod(base, exponent, modulus) ``` Contract: - `exponent >= 0` - `modulus > 0` - return the canonical value of $base^{exponent} \bmod modulus$ - use repeated squaring - do not mutate the inputs The tests compare results with a reference implementation for small inputs and include: - exponent `0`, - modulus `1`.1def canonical_mod(value, modulus):
2 return ((value % modulus) + modulus) % modulus
3
4def pow_mod(base, exponent, modulus):
5 result = canonical_mod(1, modulus) # 1 mod 1 is 0
6 current_base = canonical_mod(base, modulus)
7 current_exponent = exponent
8 while current_exponent > 0:
9 if current_exponent % 2 == 1:
10 result = canonical_mod(result * current_base, modulus)
11 current_base = canonical_mod(current_base * current_base, modulus)
12 current_exponent //= 2
13 return result
14
15def pow_nonnegative(base, exponent):
16 result, current_base, current_exponent = 1, base, exponent
17 while current_exponent > 0:
18 if current_exponent % 2 == 1:
19 result *= current_base
20 current_base *= current_base
21 current_exponent //= 2
22 return result
23
24print("3^13 mod 17 =", pow_mod(3, 13, 17))
25print("3^13 =", pow_nonnegative(3, 13))
26print("5^0 mod 7 =", pow_mod(5, 0, 7))
27print("5^0 mod 1 =", pow_mod(5, 0, 1))1public class Main {
2 static long canonicalMod(long value, long modulus) {
3 return ((value % modulus) + modulus) % modulus;
4 }
5
6 static long powMod(long base, long exponent, long modulus) {
7 long result = canonicalMod(1, modulus); // 1 mod 1 is 0
8 long currentBase = canonicalMod(base, modulus);
9 long currentExponent = exponent;
10 while (currentExponent > 0) {
11 if (currentExponent % 2 == 1) {
12 result = canonicalMod(result * currentBase, modulus);
13 }
14 currentBase = canonicalMod(currentBase * currentBase, modulus);
15 currentExponent /= 2;
16 }
17 return result;
18 }
19
20 static long powNonnegative(long base, long exponent) {
21 long result = 1, currentBase = base, currentExponent = exponent;
22 while (currentExponent > 0) {
23 if (currentExponent % 2 == 1) result *= currentBase;
24 currentBase *= currentBase;
25 currentExponent /= 2;
26 }
27 return result;
28 }
29
30 public static void main(String[] args) {
31 System.out.println("3^13 mod 17 = " + powMod(3, 13, 17));
32 System.out.println("3^13 = " + powNonnegative(3, 13));
33 System.out.println("5^0 mod 7 = " + powMod(5, 0, 7));
34 System.out.println("5^0 mod 1 = " + powMod(5, 0, 1));
35 }
36}1#include <iostream>
2using namespace std;
3
4long long canonicalMod(long long value, long long modulus) {
5 return ((value % modulus) + modulus) % modulus;
6}
7
8long long powMod(long long base, long long exponent, long long modulus) {
9 long long result = canonicalMod(1, modulus); // 1 mod 1 is 0
10 long long currentBase = canonicalMod(base, modulus);
11 long long currentExponent = exponent;
12 while (currentExponent > 0) {
13 if (currentExponent % 2 == 1) {
14 result = canonicalMod(result * currentBase, modulus);
15 }
16 currentBase = canonicalMod(currentBase * currentBase, modulus);
17 currentExponent /= 2;
18 }
19 return result;
20}
21
22long long powNonnegative(long long base, long long exponent) {
23 long long result = 1, currentBase = base, currentExponent = exponent;
24 while (currentExponent > 0) {
25 if (currentExponent % 2 == 1) result *= currentBase;
26 currentBase *= currentBase;
27 currentExponent /= 2;
28 }
29 return result;
30}
31
32int main() {
33 cout << "3^13 mod 17 = " << powMod(3, 13, 17) << endl;
34 cout << "3^13 = " << powNonnegative(3, 13) << endl;
35 cout << "5^0 mod 7 = " << powMod(5, 0, 7) << endl;
36 cout << "5^0 mod 1 = " << powMod(5, 0, 1) << endl;
37}1function canonicalMod(value, modulus) {
2 return ((value % modulus) + modulus) % modulus;
3}
4
5function powMod(base, exponent, modulus) {
6 let result = canonicalMod(1, modulus); // 1 mod 1 is 0
7 let currentBase = canonicalMod(base, modulus);
8 let currentExponent = exponent;
9 while (currentExponent > 0) {
10 if (currentExponent % 2 === 1) {
11 result = canonicalMod(result * currentBase, modulus);
12 }
13 currentBase = canonicalMod(currentBase * currentBase, modulus);
14 currentExponent = Math.floor(currentExponent / 2);
15 }
16 return result;
17}
18
19function powNonnegative(base, exponent) {
20 let result = 1, currentBase = base, currentExponent = exponent;
21 while (currentExponent > 0) {
22 if (currentExponent % 2 === 1) result *= currentBase;
23 currentBase *= currentBase;
24 currentExponent = Math.floor(currentExponent / 2);
25 }
26 return result;
27}
28
29console.log("3^13 mod 17 = " + powMod(3, 13, 17));
30console.log("3^13 = " + powNonnegative(3, 13));
31console.log("5^0 mod 7 = " + powMod(5, 0, 7));
32console.log("5^0 mod 1 = " + powMod(5, 0, 1));It runs the same loop as binary exponentiation and reduces mod m after every multiplication. For 3^13 mod 17 the state goes (1, 3, 13), (3, 9, 6), (3, 13, 3), (5, 16, 1), (12, 1, 0), so the answer is 12.
Multiply the base b times, which is O(b) work. For an exponent of 1,000,000 that is a million multiplications, while binary exponentiation needs about 20 loop passes.
Yes. Binary exponentiation, fast exponentiation and exponentiation by squaring name the same loop: square the base, halve the exponent.
Intermediate products can overflow a fixed-width integer before the final reduction. Reducing each time keeps every value below the modulus, and the result stays congruent to the true power.
13 is 1101 in binary, so 3^13 = 3^8 × 3^4 × 3^1. The loop multiplies result by the current base on each 1 bit and skips each 0 bit.