In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix.
Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation.
For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add.
This implies that it requires an amount of auxiliary memory that is roughly proportional to the number of recursive calls -- or perhaps higher if the amount of data per iteration is increasing.
The algorithms of the next section use a different approach, and the resulting algorithms needs the same number of operations, but use an auxiliary memory that is roughly the same as the memory required to store the result.
The variants described in this section are based on the formula If one applies recursively this formula, by starting with y = 1, one gets eventually an exponent equal to 0, and the desired result is then the left factor.
Each squaring results in approximately double the number of digits of the previous, and so, if multiplication of two d-digit numbers is implemented in O(dk) operations for some fixed k, then the complexity of computing xn is given by This algorithm calculates the value of xn after expanding the exponent in base 2k.
Namely, an attacker observing the sequence of squarings and multiplications can (partially) recover the exponent involved in the computation.
This is a problem if the exponent should remain secret, as with many public-key cryptosystems.
A technique called "Montgomery's ladder"[2] addresses this concern.
Given the binary expansion of a positive, non-zero integer n = (nk−1...n0)2 with nk−1 = 1, we can compute xn as follows: The algorithm performs a fixed sequence of operations (up to log n): a multiplication and squaring takes place for each bit in the exponent, regardless of the bit's specific value.
This specific implementation of Montgomery's ladder is not yet protected against cache timing attacks: memory access latencies might still be observable to an attacker, as different variables are accessed depending on the value of bits of the secret exponent.
Modern cryptographic implementations use a "scatter" technique to make sure the processor always misses the faster cache.
[3] There are several methods which can be employed to calculate xn when the base is fixed and the exponent varies.
Then the algorithm uses the equality Given the element x of G, and the exponent n written in the above form, along with the precomputed values xb0...xbw−1, the element xn is calculated using the algorithm below: If we set h = 2k and bi = hi, then the ni values are simply the digits of n in base h. Yao's method collects in u first those xi that appear to the highest power
[1] The Euclidean method was first introduced in Efficient exponentiation using precomputation and vector addition chains by P.D Rooij.
in group G, where n is a natural integer, whose algorithm is given below, is using the following equality recursively: where
In other words, a Euclidean division of the exponent n1 by n0 is used to return a quotient q and a rest n1 mod n0.
Then it raises xM to the power q, multiplies this value with xN, and then assigns xN the result of this computation and nM the value nM modulo nN.
The approach also works with semigroups that are not of characteristic zero, for example allowing fast computation of large exponents modulo a number.
Especially in cryptography, it is useful to compute powers in a ring of integers modulo q.
Applying above exp-by-squaring algorithm, with "*" interpreted as x * y = xy mod 2345 (that is, a multiplication followed by a division with remainder) leads to only 27 multiplications and divisions of integers, which may all be stored in a single machine word.
More generally, the approach works with positive integer exponents in every magma for which the binary operation is power associative.
Since the binary method computes a multiplication for every non-zero entry in the base-2 representation of n, we are interested in finding the signed-binary representation with the smallest number of non-zero entries, that is, the one with minimal Hamming weight.
One method of doing this is to compute the representation in non-adjacent form, or NAF for short, which is one that satisfies
A simple algorithm to compute the NAF representation of a given integer
More generally, if one allows any previously computed exponents to be summed (by multiplying those powers of x), one can sometimes perform the exponentiation using fewer multiplications (but typically using more memory).
The smallest power where this occurs is for n = 15: In general, finding the optimal addition chain for a given exponent is a hard problem, for which no efficient algorithms are known, so optimal chains are typically used for small exponents only (e.g. in compilers where the chains for small powers have been pre-tabulated).
However, there are a number of heuristic algorithms that, while not being optimal, have fewer multiplications than exponentiation by squaring at the cost of additional bookkeeping work and memory usage.
Regardless, the number of multiplications never grows more slowly than Θ(log n), so these algorithms improve asymptotically upon exponentiation by squaring by only a constant factor at best.