Modular Exponentiation
Computing large powers modulo n is at the heart of modern cryptography. The square-and-multiply algorithm makes this fast even for huge exponents.
The Problem: Computing 7^1000000 mod 13 naively would require a million multiplications. Square-and-multiply does it in about 20!
Square-and-Multiply Algorithm
The key insight: we can write any exponent in binary and use the fact that:
a^(2k) = (a^k)² and a^(2k+1) = a × (a^k)²
Enter values to see the algorithm in action...
How It Works
Let's trace through 3^13 mod 7 step by step:
Example: 3^13 mod 7
- 13 in binary = 1101
- Start with result = 1, base = 3
- Bit 0 = 1: result = 1 × 3 = 3, square base: 3² = 9 ≡ 2
- Bit 1 = 0: skip multiply, square base: 2² = 4
- Bit 2 = 1: result = 3 × 4 = 12 ≡ 5, square base: 4² = 16 ≡ 2
- Bit 3 = 1: result = 5 × 2 = 10 ≡ 3
- Final: 3^13 mod 7 = 3
Performance Comparison
Naive vs Square-and-Multiply
Naive Method
Click "Compare" to see...
Square-and-Multiply
Click "Compare" to see...
Why This Matters
In RSA: Encryption computes m^e mod n and decryption computes c^d mod n. With 2048-bit keys, the exponents have about 600 digits! Square-and-multiply reduces billions of operations to a few thousand.
Complexity Analysis
| Method | Multiplications | For exp = 1,000,000 |
|---|---|---|
| Naive | exp | 1,000,000 |
| Square-and-Multiply | ≤ 2 × log₂(exp) | ≤ 40 |