method of repeated squaring


Theorem 1.

Given a semigroupPlanetmathPlanetmath S and an nZ+ then the function f:SS defined by f(a)=an has an SLP representations of computational length O(log2n). Inparticular, if we can compute an using only O(log2n) multiplications.

Proof.

Let f0:SS be the map f(x)=x and f1:SS be defined by f1(x)=xx. So far we recognize that f0(x) evaluates to x1=x20 and f1(x) evaluates to x2=x21. But we caution that we do not define these functions with exponents because we want to demonstrate that from an algorithm to multiply we can create an efficient algorithm to exponentiate.

For 1<ik define (recalling that fi+1 may use the output of any previous fi evaluation)

fi+1(x):=f1(fi(x)).

Evidently, fi+1(x) evaluates to fi(x)2. By induction, fi(x) evaluates to x2i and thus fi+1(x) evaluates to (x2i)2=x2i+1. Therefore we establish that fj(x)=x2j for all nonnegative integers j. Furthermore, to evaluate fj(x) uses j multiplications.

Now write n in binary: n=a020+a121++ak2k with ai=0,1 for 0i<klog2n. Let 0i1<i2<<isk be the indices for which ait0, 1ts. Then define

gn(x)=fi1(x)fi2(x)fis(x)

Thus, gn(x) evaluates to:

(x2i1)(x2i2)(x2is) =(x20)a0(x21)a1(x2k)ak
=xa020+a121++ak2k
=xn.

Because each fi+1(x) uses the output of fi(x), the cost of evaluating gn is the cost of evaluating fis(x) plus the final cost of multiplying fi1(x)fis(x). Thus, evaluating gn uses is+(s-1) multiplications. As slog2n it follows that evaluating gn uses no more than 2log2n multiplications. ∎

Title method of repeated squaring
Canonical name MethodOfRepeatedSquaring
Date of creation 2013-03-22 16:16:14
Last modified on 2013-03-22 16:16:14
Owner Algeboy (12884)
Last modified by Algeboy (12884)
Numerical id 9
Author Algeboy (12884)
Entry type Theorem
Classification msc 20A05
Classification msc 08A99
Classification msc 20-00
Synonym successive squaring