One routine, many algebraic structures
Computing gn by repeated multiplication costs n operations; binary powering costs about log2 n squarings plus one multiplication per set bit. The algorithm requires only an associative operation with an identity, so a single implementation serves modular integers, matrices, polynomials, ideals and points on elliptic curves. Window methods and addition chains trim the multiplication count further at the cost of precomputation.
Learning objectives
- Implement both binary powering variants and state their operation counts.
- Explain why the algorithm is stated over an arbitrary monoid.
- Choose a window size that minimises total cost for a given exponent length.
- Recognise where addition chains give a genuine advantage.
- Identify the side-channel considerations that motivate the Montgomery ladder.
Section 01The generic formulation
Let (G, ·) be a monoid: an associative operation with an identity element. Powering is defined by the recursion
Nothing beyond associativity is used. Writing the routine against an abstract operation rather than against modular multiplication is not stylistic tidiness — it is what makes the same tested code compute a modular power, a Fibonacci number by matrix powering, a multiple of a point on an elliptic curve, and a power of an ideal class.
ℤ/nℤ
Modular exponentiation. Underpins Fermat and Miller–Rabin tests, RSA and Diffie–Hellman.
Matrices
Linear recurrences in logarithmic time; transfer-matrix computations.
Elliptic curve points
Written additively as scalar multiplication [n]P. Same algorithm, additive notation.
Ideal classes
Powering in the class group, the core operation of baby-step giant-step order finding.
Polynomials mod f
Computing xp mod f, the key step of distinct-degree factorisation.
Permutations
Powers of group elements in computational group theory.
Section 02The two binary variants
Both process the binary expansion of the exponent; they differ in direction and in what they must keep alive.
- Write n in binary as (nk−1 … n0)2 with nk−1 = 1.
- Set y ← g.
- For i from k−2 down to 0: set y ← y2.
- If ni = 1, set y ← y · g. The multiplier is always the fixed base g.
- Return y.
- Set y ← 1 and z ← g.
- While n > 0:
- If n is odd, set y ← y · z.
- Set n ← ⌊n / 2⌋.
- If n > 0, set z ← z2. z holds the running square g2^i.
- Return y.
| Criterion | Left-to-right | Right-to-left |
|---|---|---|
| Live values | One accumulator plus fixed base | Two accumulators |
| Exponent known in advance? | Must know the bit length | Not required |
| Extends to window methods | Yes — the natural choice | Awkward |
| Multiplier operand | Always g — may be small and cheap | Grows each step |
Section 03Window methods
Set bits are cheaper in groups. Precompute the odd powers g1, g3, …, g2w−1, then scan the exponent in windows of up to w bits, squaring between windows and multiplying once per window. A sliding window aligns each window to start and end on a set bit, which reduces the number of windows further.
The optimal w grows slowly with exponent length: window sizes of 4 to 6 cover most practical exponents. The precomputation table is only worth building when the same base is raised to a long exponent, so fixed-base workloads benefit most.
Window methods trade memory for time. On constrained hardware the table may not fit, and plain binary powering is then correct by default. Measure before assuming a window helps.
Section 04Addition chains and their limits
An addition chain for n is a sequence starting at 1 in which every term is a sum of two earlier terms and which ends at n. The length of the shortest chain is the minimum number of multiplications needed. Binary powering yields a chain, but not always the shortest: for n = 15 the binary method uses six multiplications while a chain of length five exists.
Finding shortest addition chains is itself hard, and the saving over a sliding window is typically a few percent. Addition chains are worth the effort only when a single fixed exponent is used enormously often — a fixed public exponent, or a fixed curve parameter — so the chain can be computed once, offline.
Section 05Constant-time powering
The binary method's running time depends on the exponent's bit pattern, which leaks the exponent through timing and power measurement. Where the exponent is secret, the Montgomery ladder is used instead: it performs one squaring and one multiplication per bit regardless of the bit's value, maintaining the invariant that the two registers hold consecutive powers.
- Set R0 ← 1 and R1 ← g.
- For i from k−1 down to 0:
- If ni = 0: R1 ← R0·R1; R0 ← R02.
- If ni = 1: R0 ← R0·R1; R1 ← R12. Both branches cost the same.
- Return R0.
A constant-time ladder built on a modular multiplication with data-dependent branches leaks anyway. Constant-time behaviour must hold at every layer, including the multiprecision routines and any conditional normalisation.
ReferenceFrequently asked questions
Does the algorithm work when the exponent is zero or negative?
Zero returns the identity by convention. Negative exponents require the element to be invertible: compute the inverse first, then raise to the absolute value. In a monoid that is not a group, negative exponents are simply undefined and the routine should reject them.
How many multiplications does binary powering use on average?
About half the bits of a random exponent are set, so the expected count is roughly k squarings and k/2 multiplications for a k-bit exponent — approximately 1.5k operations in total, against n for the naive method.
Should squarings be counted separately from multiplications?
Yes. In most structures squaring is measurably cheaper than general multiplication — notably for multiprecision integers and for elliptic curve points — so a cost model that conflates them will choose the wrong window size.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
Treatments appear in Knuth volume 2 and in Cohen's A Course in Computational Algebraic Number Theory. Side-channel aspects are covered in the applied cryptography literature.
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.