How does the Square-and-Multiply (SAM) algorithm work for efficient modular exponentiation?
SAM computes $a^m \mod N$ by converting the exponent to binary, then processing each bit: square for every bit, additionally multiply for each "1" bit — reducing mod N at every step.
* Square-and-Multiply computing 5²² mod 11: walk the exponent's bits (10110) left to right, squaring every step and multiplying on each 1-bit, reducing mod 11 throughout. *
Algorithm:
- Write the exponent $m$ in binary
- Skip the leading "1"
- For each remaining bit (left to right):
- "0": Square the accumulator
- "1": Square the accumulator, then multiply by $a$
- Reduce mod N after every operation
Example: $5^{22} \mod 11$ where $22 = (10110)_2$
| Bit | Operation | Exponent (without mod) |
|---|---|---|
| 1 | Start with $5^1$ | $5^1$ |
| 0 | Square: $5^2 \equiv 3 \mod 11$ | $5^2$ |
| 1 | Square then multiply: $3^2 \cdot 5 \equiv 1 \mod 11$ | $5^5$ |
| 1 | Square then multiply: $1^2 \cdot 5 \equiv 5 \mod 11$ | $5^{11}$ |
| 0 | Square: $5^2 \equiv 3 \mod 11$ | $5^{22}$ |
Result: $5^{22} \equiv 3 \mod 11$
Efficiency: For a $k$-bit exponent: approximately $k$ squarings + $k/2$ multiplications. For 3072-bit RSA: about 3071 squarings + ~1535 multiplications ≈ 4600 operations total. Without SAM, you'd need $2^{3072}$ multiplications — utterly impossible.
Go deeper:
Exponentiation by squaring (Wikipedia) — the general algorithm behind fast modular powers.