Engineering / Mathematics — Integer Algorithms
Modular Exponentiation by Repeated Squaring
Square-and-multiply exponentiation, its cost, windowed variants, and the side-channel hazards of the naive form.
Executive summary
Modular exponentiation with an exponent of k bits costs about k squarings and at most k multiplications, rather than the exponentially many implied by repeated multiplication. It is the primitive on which RSA, Diffie-Hellman and Miller-Rabin all rest.
The naive implementation leaks the exponent through timing and power consumption, which for a private key is fatal.
Learning objectives
- State and justify the square-and-multiply algorithm.
- Compute the cost in modular multiplications.
- Identify the side-channel weakness and its standard mitigations.
01The algorithm
Left-to-right square and multiply
base a, exponent e with k bits, modulus na^e mod n- Write the exponent e in binary as e_{k−1} ... e₀, with e_{k−1} = 1.
- Set r = a.
- For i from k−2 down to 0:
- Set r = r² mod n.
- If eᵢ = 1, set r = r · a mod n.
- Return r.
k − 1 squarings and (weight(e) − 1) multiplicationsCorrectness is an invariant argument: after processing the top j bits, r equals a raised to the integer formed by those bits. Squaring doubles that integer; multiplying by a adds one.
Cost ≈ k squarings + k/2 multiplications on average ⇒ O(k · len(n)²) bit operations02Windowed and fixed-base variants
Processing several exponent bits at once reduces the multiplication count at the cost of precomputed powers.
| Method | Precomputation | Multiplications | Use case |
|---|---|---|---|
| Binary | none | ≈ k/2 | One-off exponentiation, minimal memory |
| Fixed window, width w | 2^w − 2 powers | ≈ k/w | General speedup |
| Sliding window | odd powers only | ≈ k/(w+1) | Best general-purpose choice |
| Fixed base | table of a^{2^i} | ≈ k/w | Same base reused, e.g. a group generator |
03Side channels
Three mitigations are standard, and they compose.
- Always-multiply. Perform the multiplication unconditionally and discard the result when the bit is 0. Costs a full extra multiplication per bit but removes the timing signal.
- Montgomery ladder. Maintain two values and perform one squaring and one multiplication per bit regardless of its value, with only the assignment target depending on the bit.
- Blinding. Randomise the base or the exponent before the computation so that repeated measurements cannot be correlated. For RSA, exponent blinding adds a random multiple of φ(n) to the exponent.
Constant-time discipline extends further than the exponentiation loop: the underlying modular multiplication and any conditional subtraction must also avoid data-dependent branches and memory access patterns.
04Frequently asked questions
Left-to-right or right-to-left?
Left-to-right allows the multiplier to remain the fixed base a, which enables fixed-base precomputation and keeps one operand small if a is small. Right-to-left squares a running value independent of the accumulator, which parallelises better. Left-to-right is the more common choice.
Can the exponent be reduced first?
Modulo φ(n) when the base is coprime to n, by Euler's theorem. This is worthwhile when the exponent is much larger than the modulus, and it is how RSA keeps private exponents bounded.
Does the Chinese remainder theorem help here?
For RSA decryption, substantially. Exponentiating modulo p and q separately and recombining costs roughly a quarter of the full computation, since the operands are half length and multiplication is quadratic. It requires the factorisation, so only the key holder benefits.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 48-51.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.