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. These can be of quite general use, for example in modular arithmetic or powering of matrices. 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.
The method is based on the observation that, for any integer
n>0
If the exponent is zero then the answer is 1. If the exponent is negative then we can reuse the previous formula by rewriting the value using a positive exponent. That is,
Together, these may be implemented directly as the following recursive algorithm:
In: an integer x; an integer n Out: xn exp_by_squaring(x, n) if n < 0 then return exp_by_squaring(1 / x, -n); else if n = 0 then return 1; else if n is even then return exp_by_squaring(x * x, n / 2); else if n is odd then return x * exp_by_squaring(x * x, (n - 1) / 2); end function
In each recursive call, the least significant digits of the binary representation of is removed. It follows that the number of recursive calls is
\lceillog2n\rceil,
This algorithm is not tail-recursive. 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
yxn= \begin{cases} (yx)(x2)(n,&ifnisodd\\ y(x2)n/2,&ifniseven. \end{cases}
If one applies recursively this formula, by starting with, one gets eventually an exponent equal to, and the desired result is then the left factor.
This may be implemented as a tail-recursive function:
The iterative version of the algorithm also uses a bounded auxiliary space, and is given by
The correctness of the algorithm results from the fact that
yxn
1 ⋅ xn=xn
yx1=xy
These algorithms use exactly the same number of operations as the algorithm of the preceding section, but the multiplications are done in a different order.
A brief analysis shows that such an algorithm uses
\lfloorlog2n\rfloor
\lfloorlog2n\rfloor
\lfloor \rfloor
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
O(logn) | |
\sum\limits | |
i=0 |
(2iO(logx))k=O((nlogx)k).
This algorithm calculates the value of xn after expanding the exponent in base 2k. It was first proposed by Brauer in 1939. In the algorithm below we make use of the following function f(0) = (k, 0) and f(m) = (s, u), where m = u·2s with u odd.
Algorithm:
x3,x5,...,
2k-1 | |
x |
y := 1; i := l - 1 while i ≥ 0 do (s, u) := f(ni) for j := 1 to k - s do y := y2 y := y * xu for j := 1 to s do y := y2 i := i - 1 return y
For optimal efficiency, k should be the smallest integer satisfying[1]
lgn<
k(k+1) ⋅ 22k | |
2k+1-k-2 |
+1.
This method is an efficient variant of the 2k-ary method. For example, to calculate the exponent 398, which has binary expansion (110 001 110)2, we take a window of length 3 using the 2k-ary method algorithm and calculate 1, x3, x6, x12, x24, x48, x49, x98, x99, x198, x199, x398.But, we can also compute 1, x3, x6, x12, x24, x48, x96, x192, x199, x398, which saves one multiplication and amounts to evaluating (110 001 110)2
Here is the general algorithm:
Algorithm:
x3,x5,...
2k-1 | |
,x |
Algorithm:
y := 1; i := l - 1 while i > -1 do if ni = 0 then y := y2' i := i - 1 else s := max while ns = 0 do s := s + 1[2] for h := 1 to i - s + 1 do y := y2 u := (ni, ni-1, ..., ns)2 y := y * xu i := s - 1 return y
Many algorithms for exponentiation do not provide defence against side-channel attacks. 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"[3] 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: x1 = x; x2 = x2 for i = k - 2 to 0 do if ni = 0 then x2 = x1 * x2; x1 = x12 else x1 = x1 * x2; x2 = x22 return x1
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. A similar algorithm for multiplication by doubling exists.
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.[4]
There are several methods which can be employed to calculate xn when the base is fixed and the exponent varies. As one can see, precomputations play a key role in these algorithms.
Yao's method is orthogonal to the -ary method where the exponent is expanded in radix and the computation is as performed in the algorithm above. Let,,, and be integers.
Let the exponent be written as
n=
w-1 | |
\sum | |
i=0 |
nibi,
0\leqslantni<h
i\in[0,w-1]
Let .
Then the algorithm uses the equality
xn=
w-1 | |
\prod | |
i=0 |
ni | |
x | |
i |
=
h-1 | |
\prod | |
j=1 |
[\prod | |
ni=j |
j. | |
x | |
i] |
Given the element of, and the exponent written in the above form, along with the precomputed values, the element is calculated using the algorithm below:
y = 1, u = 1, j = h - 1 while j > 0 do for i = 0 to w - 1 do if ni = j then u = u × xbi y = y × u j = j - 1 return y
If we set and, then the values are simply the digits of in base . Yao's method collects in u first those that appear to the highest power ; in the next round those with power are collected in as well etc. The variable y is multiplied times with the initial, times with the next highest powers, and so on.The algorithm uses multiplications, and elements must be stored to compute .
The Euclidean method was first introduced in Efficient exponentiation using precomputation and vector addition chains by P.D Rooij.
This method for computing
xn
n0 | |
x | |
0 |
⋅
n1 | |
x | |
1 |
=\left(x0 ⋅
q\right) | |
x | |
1 |
n0 | |
⋅
n1\modn0 | |
x | |
1 |
,
q=\left\lfloor
n1 | |
n0 |
\right\rfloor
Given the base element in group, and the exponent
n
xn
l
b0 | |
x |
,...,
| |||||
x |
Begin loop Break loop End loop;
The algorithm first finds the largest value among the and then the supremum within the set of .Then it raises to the power, multiplies this value with, and then assigns the result of this computation and the value modulo .
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 . For example, the evaluation of
would take a very long time and much storage space if the naïve method of computing and then taking the remainder when divided by 2345 were used. Even using a more effective method will take a long time: square 13789, take the remainder when divided by 2345, multiply the result by 13789, and so on.
Applying above exp-by-squaring algorithm, with "*" interpreted as (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. Generally, any of these approaches will take fewer than modular multiplications.
The approach can also be used to compute integer powers in a group, using either of the rules
,
.
The approach also works in non-commutative semigroups and is often used to compute powers of matrices.
More generally, the approach works with positive integer exponents in every magma for which the binary operation is power associative.
In certain computations it may be more efficient to allow negative coefficients and hence use the inverse of the base, provided inversion in is "fast" or has been precomputed. For example, when computing, the binary method requires multiplications and squarings. However, one could perform squarings to get and then multiply by to obtain .
To this end we define the signed-digit representation of an integer in radix as
n=
l-1 | |
\sum | |
i=0 |
nibiwith|ni|<b.
Signed binary representation corresponds to the particular choice and
ni\in\{-1,0,1\}
(nl-1...n0)s
(10\bar11100\bar110)s
(100\bar11000\bar10)s
\bar1
nini+1=0foralli\geqslant0
(nl-1...n0)NAF
(1000\bar1000\bar10)NAF
n=(nlnl-1...n0)2
nl=nl-1=0
for to do
Another algorithm by Koyama and Tsuruoka does not require the condition that
ni=ni+1=0
See main article: Addition-chain exponentiation. Exponentiation by squaring can be viewed as a suboptimal addition-chain exponentiation algorithm: it computes the exponent by an addition chain consisting of repeated exponent doublings (squarings) and/or incrementing exponents by one (multiplying by x) only. 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:
x15=x x (x x [x x x2]2)2
x15=x3 x ([x3]2)2
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.
2k-1 | |
x |