Fast Modular Powers: Repeated Squaring
Computing 13²⁷ as an ordinary integer creates a large number only to discard almost all of it when taking a remainder. Repeated squaring keeps the part we need at every step.
The trick is to make powers a¹,a²,a⁴,a⁸,…. Each is the square of the previous one. Write the requested exponent as a sum of powers of two, then multiply the corresponding results. Since addition and multiplication preserve congruence, every intermediate value may be reduced modulo n.
Decrypting the future RSA example
We want 13²⁷ (mod 55). Here are the actual reduced squares:
| Power | Calculation from previous residue | Residue modulo 55 |
|---|---|---|
| 1 | Start with 13 | 13 |
| 2 | 13²=169=3×55+4 | 4 |
| 4 | 4²=16 | 16 |
| 8 | 16²=256=4×55+36 | 36 |
| 16 | 36²=1296=23×55+31 | 31 |
Because 27=16+8+2+1, select the residues 31, 36, 4 and 13. The power-4 row helps us compute higher squares but is not part of the final product.
Check the three reductions: 31×36=1116=20×55+16; 16×4=64=55+9; 9×13=117=2×55+7. No step needs the full integer 13²⁷.
Why it scales
An exponent with k binary digits needs about k squaring stages, plus at most k selected multiplications, instead of a number of multiplications proportional to the exponent itself. The intermediate residues remain below n; a product before reduction can be as large as (n-1)².
This makes the modular exponentiation operations in RSA practical even when the exponent has hundreds or thousands of bits. It does not make every inverse problem easy: efficient forward computation is different from recovering a secret exponent or factoring a modulus.
The method explains how to calculate the power. Euler's theorem explains why a carefully chosen exponent returns the original message.