Exponentiation by squaring - AbsoluteAstronomy.com

Exponentiating by squaring is a general method for fast computation of large integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

powers of a number

Number

A number is a mathematical object used to count and measure. In mathematics, the definition of number has been extended over the years to include such numbers as zero, negative numbers, rational numbers, irrational numbers, and complex numbers....

. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. In additive

Additive group

An additive group may refer to:*an abelian group, when it is written using the symbol + for its binary operation*a group scheme representing the underlying-additive-group functor...

notation the appropriate term is double-and-add. These can be of quite general use: for example in modular arithmetic

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

or powering of matrices.

Underlying idea

Using the following observation, one can create a recursive algorithm

Recursion

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

that computes xⁿ for an integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

n using squaring and multiplication:

A brief analysis shows that such an algorithm uses log₂n squarings and at most log₂n multiplications. For n > about 4 this is computationally more efficient than naïvely multiplying the base with itself repeatedly.

2^k-ary Method

This algorithm calculates the value of xⁿ after expanding the exponent in base 2^k. It was first proposed by Brauer

Brauer

Brauer or Bräuer is a surname of German origin, meaning "brewer". Notable people with the name include:* Arik Brauer , Austrian painter, poet, and actor, father of Timna 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·2^s
with u odd.

Algorithm:

Input: An element x of G, a parameter k > 0, a non-negative integer n = (n_l−1, n_l−2, ..., n₀)_2^k and the precomputed values x³, x⁵, ...,

x^{2^k-1}

.

Output: The element xⁿ in G

1. y := 1 and i := l-1
2. While i>=0 do
3. (s,u) := f(n_i)
4. for j:=1 to k-s do
5. y := y²
6. y := y*x^u
7. for j:=1 to s do
8. y := y²
9. i := i-1
10. return y

For optimal efficiency, k should be the smallest integer satisfying

Sliding Window Method

This method is an efficient variant of the 2^k-ary method. For example, to calculate the exponent 398 which has binary expansion (110 001 110)₂, we take a window of length 3 using the 2^k-ary method algorithm we calculate 1,x³,x⁶,x¹²,x²⁴,x⁴⁸,x⁴⁹,x⁹⁸,x⁹⁹,x¹⁹⁸,x¹⁹⁹,x³⁹⁸.
But, we can also compute 1,x³,x⁶,x¹²,x²⁴,x⁴⁸,x⁹⁶,x¹⁹²,x¹⁹⁹,
x³⁹⁸ which saves one multiplication and amounts to evaluating (110 001 110)n₂

Here is the general algorithm:

Algorithm:

Input:An element 'x' of 'G',a non negative integer n=(n_i,n_i-1,...,n₀)₂, a parameter k>0 and the pre-computed values x³,x⁵,...

x^{2^k-1}

.

Output: The element xⁿ in G

Algorithm:

1. y := 1 and i := l-1
2. while i > -1 do
3. if n_i=0 then y:=y² and i:=i-1
4. else
5. s:=max{i-k+1,0}
6. while n_s=0 do s:=s+1
7. for h:=1 to i-s+1 do y:=y²
8. u:=(n_i,n_i-1,....,n_s)₂
9. y:=y*x^u
10. i:=s-1
11. return y

Note:

In line 6 the loop finds the longest string of length less than or equal to 'k' which ends in a non zero value. Also not all odd powers of 2 up to $x^{2^k-1}$ need be computed and only those specifically involved in the computation need be considered.

Montgomery's Ladder Technique

Many algorithms for exponentiation do not provide defense 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

Public-key cryptography

Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...

. A technique called Montgomery's

Peter Montgomery

Peter Lawrence Montgomery is an American mathematician who has published widely in the more mathematical end of the field of cryptography. He is currently a researcher in the cryptography group at Microsoft Research....

Ladder addresses this concern.

Given the binary expansion of a positive, non-zero integer n=(n_k-1...n₀)₂ with n_k-1=1 we can compute xⁿ as follows:
x₁=x; x₂=x²
for i=k-2 to 0 do
If n_i=0 then
x₂=x₁*x₂; x₁=x₁²
else
x₁=x₁*x₂; x₂=x₂²
return x₁

The algorithm performs a fixed sequence of operations (up to

Up to

In mathematics, the phrase "up to x" means "disregarding a possible difference in x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...

log n): a multiplication and squaring takes place for each bit in the exponent, regardless of the bit's specific value.

Fixed Base Exponent

There are several methods which can be employed to calculate xⁿ when the base is fixed and the exponent varies. As one can see, precomputation

Precomputation

In algorithms, precomputation is the act of performing an initial computation before run time to generate a lookup table that can be used by an algorithm to avoid repeated computation each time it is executed. Precomputation is often used in algorithms that depend on the results of expensive...

s play a key role in these algorithms.

Yao's Method

Yao's method is orthogonal to the 2^k-ary method where the exponent is expanded in radix b=2^k and the computation is as performed in the algorithm above. Let "n", "n_i", "b", and "b_i" be integers.
Let the exponent "n" be written as

where

for all

Let x_i = x^b_i. Then the algorithm uses the equality

Given the element 'x' of G, and the exponent 'n' written in the above form, along with the pre computed values x^b₀....x^b_l-1 the element xⁿ is calculated using the algorithm below

y=1,u=1 and j=h-1
while j > 0 do
for i=0 to l-1 do
1. if n_i=j then u=u*x^b_i
y=y*u
j=j-1
return y

If we set h=2^k and b_i = hⁱ then the n_i 's are simply the digits of n in base h. Yao's method collects in u first those x_i which appear to the highest power h-1; in the next round those with power h-2 are collected in u as well etc. The variable y is multiplied h-1 times with the initial u, h-2 times with the next highest powers etc.
The algorithm uses l+h-2 multiplications and l+1 elements must be stored to compute xⁿ (see ).

Euclidean Method

The Euclidean method was first introduced in 'Efficient exponentiation using precomputation and vector addition chains' by P.D Rooij. The algorithm below computes xⁿ using the following equality recursively

where q=

Given the element x in G and the exponent 'n' written as in Yao's method with the pre computed values x^b₀....x^b_l-1 the element xⁿ is calculated using the algorithm below

while true do
Find M such that n_M ≥ n_i for all i in [0,l-1]
Find N ≠ M such that n_N ≥ n_i for all i in [0,l-1], i ≠ M
if n_N ≠ 0 then
q= (n_M/n_N), x_N=x_M^q·x_N and n_M=n_N mod n_N
else break
return x_M^n_M

The algorithm first finds the largest value amongst the n_i and then the supremum within the set of {n_i : i ≠ M }. It raises x_M to the power q, multiplies this value with x_N, and then assigns x_N the result of this computation and n_M the value n_M modulo n_N.

Further applications

The same idea allows fast computation of large exponents modulo

Modular exponentiation

Modular exponentiation is a type of exponentiation performed over a modulus. It is particularly useful in computer science, especially in the field of cryptography....

a number. Especially in cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, it is useful to compute powers in a ring

Ring (mathematics)

In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...

of integers modulo q

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

. It can also be used to compute integer powers in a group

Group (mathematics)

In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

, using the rule

Power(x, −n) = (Power(x, n))⁻¹.

The method works in every semigroup

Semigroup

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...

and is often used to compute powers of matrices,

For example, the evaluation of

13789⁷²²³⁴¹ (mod 2345)

would take a very long time and lots of storage space if the naïve method were used: compute 13789⁷²²³⁴¹ then take the remainder

Remainder

In arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient....

when divided by 2345. Even using a more effective method will take a long time: square 13789, take the remainder when divided by 2345, multiply the result

Result

A result is the final consequence of a sequence of actions or events expressed qualitatively or quantitatively. Possible results include advantage, disadvantage, gain, injury, loss, value and victory. There may be a range of possible outcomes associated with an event depending on the point of...

by 13789, and so on. This will take 722340 modular multiplications. The square-and-multiply algorithm is based on the observation that 13789⁷²²³⁴¹ = 13789(13789²)³⁶¹¹⁷⁰. So, if we computed 13789², then the full computation would only take 361170 modular multiplications. This is a gain of a factor of two. But since the new problem is of the same type, we can apply the same observation again, once more approximately halving the size.

The repeated application of this algorithm is equivalent to decomposing the exponent (by a base conversion to binary) into a sequence of squares and products: for example

x¹³ = x^1101_bin

= x^{(1·2^3 + 1·2^2 + 0·2^1 + 1·2^0)}

= x^{1·2^3} · x^{1·2^2} · x^{0·2^1} · x^{1·2^0}

= x^{2^3} · x^{2^2} · 1 · x^{2^0}

= x⁸ · x⁴ · x¹

= (x⁴)² · (x²)² · x

= (x⁴ · x²)² · x

= ((x²)² · x²)² · x

= ((x² · x)²)² · x → algorithm needs only 5 multiplications instead of 12 (13−1)

Some more examples:

x¹⁰ = ((x²)²·x)² because 10 = (1,010)₂ = 2³+2¹, algorithm needs 4 multiplications instead of 9
x¹⁰⁰ = (((((x²·x)²)²)²·x)²)² because 100 = (1,100,100)₂ = 2⁶+2⁵+2², algorithm needs 8 multiplications instead of 99
x^1,000 = ((((((((x²·x)²·x)²·x)²·x)²)²·x)²)²)² because 10³ = (1,111,101,000)₂, algorithm needs 14 multiplications instead of 999
Worked example (with modulo) for the RSA algorithm.

Computation by powers of 2

This is a non-recursive implementation of the above algorithm in Ruby

Ruby (programming language)

Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...

.

In most statically typed languages, result=1 must be replaced with code assigning an identity matrix

Identity matrix

In linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...

of the same size as x to result to get a matrix exponentiating algorithm. In Ruby, thanks to coercion, result is automatically upgraded to the appropriate type, so this function works with matrices as well as with integers and floats. Note that n=n1 is redundant when n=n/2 implicitly rounds towards zero, as lower level languages would do.
n[0] is the rightmost bit of the binary representation of n, so if it is 1, the number is odd, if it is zero, the number is even.

def power(x,n)
result = 1
while n.nonzero?
if n[0].nonzero?
result *= x
n -= 1
end
x *= x
n /= 2
end
return result
end

Runtime example: Compute 3¹⁰

parameter x = 3
parameter n = 10
result := 1

Iteration 1
n = 10 -> n is even
x := x² = 3² = 9
n := n / 2 = 5

Iteration 2
n = 5 -> n is odd
-> result := result * x = 1 * x = 1 * 3² = 9
n := n - 1 = 4
x := x² = 9² = 3⁴ = 81
n := n / 2 = 2

Iteration 3
n = 2 -> n is even
x := x² = 81² = 3⁸ = 6561
n := n / 2 = 1

Iteration 4
n = 1 -> n is odd
-> result := result * x = 3² * 3⁸ = 3¹⁰ = 9 * 6561 = 59049
n := n - 1 = 0

return result

Runtime example: Compute 3¹⁰

result := 3
bin := "1010"

Iteration for digit 2:
result := result² = 3² = 9
1010_bin - Digit equals "0"

Iteration for digit 3:
result := result² = (3²)² = 3⁴ = 81
1010_bin - Digit equals "1" --> result := result*3 = (3²)²*3 = 3⁵ = 243

Iteration for digit 4:
result := result² = ((3²)²*3)² = 3¹⁰ = 59049
1010_bin - Digit equals "0"

return result

JavaScript-Demonstration: http://home.mnet-online.de/wzwz.de/temp/ebs/en.htm

Calculation of products of powers

Exponentiation by squaring may also be used to calculate the product of 2 or more powers.
If the underlying group or semigroup is commutative then it is often possible to reduce the
number of multiplication by computing the product simultaneously.

Example

The formula a⁷×b⁵ may be calculated within 3 steps:²×a)²×a (four multiplications for calculating a⁷)²)²×b (three multiplications for calculating b⁵)

(a⁷)×(b⁵) (one multiplication to calculate the product of the two)

so one gets eight multiplications in total.

A faster solution is to calculate both powers simultaneously:²×a)²×a×b
which needs only 6 multiplications in total. Note that a×b is calculated twice, the result could be stored after the first calculation which reduces the count of multiplication to 5.

Example with numbers:

2⁷×3⁵ = ((2×3)²×2)²×2×3 = (6²×2)²×6 = 72²×6 = 31,104

Calculating the powers simultaneously instead of calculating them separately always reduces the
count of multiplications if at least two of the exponents are greater than 1.

Using transformation

The example above a⁷×b⁵ may also be calculated with only 5
multiplications if the expression is transformed before calculation:

a⁷×b⁵ = a²×(ab)⁵ with ab := a×b

ab := a×b (one multiplication)

a²×(ab)⁵ = ((ab)²×a)²×ab (four multiplications)

Generalization of transformation shows the following scheme:

For calculating a^A×b^B×...×m^M×n^N

1st: define ab := a×b, abc = ab×c, ...

2nd: calculate the transformed expression a^A−B×ab^B−C×...×abc..m^M−N×abc..mn^N

Transformation before calculation often reduces the count of multiplications
but in some cases it also increases the count (see the last one of the examples below),
so it may be a good idea to check the count of multiplications before using the transformed expression for calculation.

Examples

For the following expressions the count of multiplications is shown for calculating each power separately,
calculating them simultaneously without transformation and calculating them simultaneously after transformation.

Example: a⁷×b⁵×c³

separate: [((a)²×a)²×a] × [((b)²)²×b] × [(c)²×c] ( 11 multiplications )

simultaneous: ((a×b)²×a×c)²×a×b×c ( 8 multiplications )

transformation: a := 2 ab := a×b abc := ab×c ( 2 multiplications )

calculation after that: (a×ab×abc)²×abc ( 4 multiplications ⇒ 6 in total )

Example: a⁵×b⁵×c³

separate: [((a)²)²×a] × [((b)²)²×b] × [(c)²×c] ( 10 multiplications )

simultaneous: ((a×b)²×c)²×a×b×c ( 7 multiplications )

transformation: a := 2 ab := a×b abc := ab×c ( 2 multiplications )

calculation after that: (ab×abc)²×abc ( 3 multiplications ⇒ 5 in total )

Example: a⁷×b⁴×c¹

separate: [((a)²×a)²×a] × [((b)²)²] × [c] ( 8 multiplications )

simultaneous: ((a×b)²×a)²×a×c ( 6 multiplications )

transformation: a := 2 ab := a×b abc := ab×c ( 2 multiplications )

calculation after that: (a×ab)²×a×ab×abc ( 5 multiplications ⇒ 7 in total )

Signed-digit recoding

In certain computations it may be more efficient to allow negative coefficients and hence use the inverse of the base, provided inversion in G is ' fast' or has been precomputed. For example, when computing x^{2^k−1} the binary method requires k−1 multiplications and k−1 squarings . However one could perform k squarings to get x^{2^k} and then multiply by x⁻¹ to obtain x^{2^k−1}.

To this end we define the signed-digit representation

Signed-digit representation

Signed-digit representation of numbers indicates that digits can be prefixed with a − sign to indicate that they are negative.Signed-digit representation can be used in low-level software and hardware to accomplish fast addition of integers because it can eliminate carries...

of an integer

in radix

'Signed Binary Representation' corresponds to the particular choice

and

. It is denoted by

. There are several methods for computing this representation. The representation is not unique, for example take

. Two distinct signed-binary representations are given by

and

, where

is used to denote

. Since the binary method computes a multiplication for every non-zero entry in the base 2 representation of

, 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

Hamming weight

The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string of bits, this is the number of 1's in the string...

. One method of doing this is to compute the representation in non-adjacent form

Non-adjacent form

The non-adjacent form of a number is a unique signed-digit representation. Like the name suggests, non-zero values cannot be adjacent. For example:2 = 4 + 2 + 1 = 72 = 8 − 2 + 1 = 72 = 8 − 4 + 2 + 1 = 72 = 8 − 1 = 7...

, or NAF for short, which is one that satisfies

and denoted by

. For example the NAF representation of 478 is equal to

. This representation always has minimal Hamming weight. A simple algorithm to compute the NAF representation of a given integer

with

is the following:

for to do
return

Another algorithm by Koyama and Tsuruoka does not require the condition that

; it still minimizes the Hamming weight.

Alternatives and generalizations

Exponentiation by squaring can be viewed as a suboptimal addition-chain exponentiation

Addition-chain exponentiation

In mathematics and computer science, optimal addition-chain exponentiation is a method of exponentiation by positive integer powers that requires a minimal number of multiplications. It works by creating a shortest addition chain that generates the desired exponent. Each exponentiation in the chain...

algorithm: it computes the exponent via an addition chain

Addition chain

In mathematics, an addition chain for computing a positive integer n can be given by a sequence of natural numbers v and a sequence of index pairs w such that each term in v is the sum of two previous terms, the indices of those terms being specified by w:Often only v is given since it is easy to...

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:

(squaring, 6 multiplies)

(optimal addition chain, 5 multiplies if x³ is re-used)

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 only used for small exponents (e.g. in compiler

Compiler

A compiler is a computer program that transforms source code written in a programming language into another computer language...

s where the chains for small powers have been pre-tabulated). However, there are a number of heuristic

Heuristic

Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...

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 only improve asymptotically upon exponentiation by squaring by a constant factor at best.

Underlying idea

2k-ary Method

Sliding Window Method

Montgomery's Ladder Technique

Fixed Base Exponent

Yao's Method

Euclidean Method

Further applications

Computation by powers of 2

Runtime example: Compute 310

Runtime example: Compute 310

Calculation of products of powers

Example

Using transformation

Examples

Signed-digit recoding

Alternatives and generalizations

See also

2^k-ary Method

Runtime example: Compute 3¹⁰

Runtime example: Compute 3¹⁰