Multiprecision Arithmetic
Binary Powering and Exponentiation Chains
Square-and-multiply exponentiation, left-to-right and right-to-left variants, windowing, and why exponentiation cost drives primality testing.
Engineering / MathematicsMultiprecision Arithmetic2 min readKV-MATH-0511
Raising an element to a large power appears in almost every algorithm here: pseudoprime tests, discrete logarithms, order computations and the elliptic curve method. Doing it by repeated multiplication is hopeless; binary powering makes it logarithmic.
The basic method
Write the exponent in binary. Squaring the base repeatedly produces the powers of two; multiplying together those corresponding to set bits produces the result.
Right-to-left binary powering
- InitialiseResult is the identity; running value is the base.
- Scan bitsFor each bit of the exponent from least significant.
- Multiply on set bitIf the bit is set, multiply the result by the running value.
- Square alwaysSquare the running value and move to the next bit.
Left-to-right variant
Scanning from the most significant bit instead squares the accumulator and multiplies by the original base when a bit is set. This requires only one working value rather than two, and the multiplier is always the fixed base — which matters when that base is small enough for a cheaper multiplication routine.
| Variant | Working values | Multiplier | Best when |
|---|---|---|---|
| Right-to-left | Two | Varies | Exponent arrives least significant first |
| Left-to-right | One | Fixed base | Base is small, or memory is tight |
Windowing
Processing several exponent bits at a time reduces the number of multiplications at the cost of precomputing small powers of the base. For a window of w bits, precompute the odd powers up to 2^w, then scan the exponent in windows.
Cost
Side channels
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.2. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.