# method of repeated squaring

###### Theorem 1.

Given a semigroup $S$ and an $n\in\mathbb{Z}^{+}$ then the function $f:S\rightarrow S$ defined by $f(a)=a^{n}$ has an SLP representations of computational length $O(\log_{2}n)$. Inparticular, if we can compute $a^{n}$ using only $O(\log_{2}n)$ multiplications.

###### Proof.

Let $f_{0}:S\rightarrow S$ be the map $f(x)=x$ and $f_{1}:S\rightarrow S$ be defined by $f_{1}(x)=xx$. So far we recognize that $f_{0}(x)$ evaluates to $x^{1}=x^{2^{0}}$ and $f_{1}(x)$ evaluates to $x^{2}=x^{2^{1}}$. 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 define (recalling that $f_{i+1}$ may use the output of any previous $f_{i}$ evaluation)

 $f_{i+1}(x):=f_{1}(f_{i}(x)).$

Evidently, $f_{i+1}(x)$ evaluates to $f_{i}(x)^{2}$. By induction, $f_{i}(x)$ evaluates to $x^{2^{i}}$ and thus $f_{i+1}(x)$ evaluates to $(x^{2^{i}})^{2}=x^{2^{i+1}}$. Therefore we establish that $f_{j}(x)=x^{2^{j}}$ for all nonnegative integers $j$. Furthermore, to evaluate $f_{j}(x)$ uses $j$ multiplications.

Now write $n$ in binary: $n=a_{0}2^{0}+a_{1}2^{1}+\cdots+a_{k}2^{k}$ with $a_{i}=0,1$ for $0\leq i. Let $0\leq i_{1} be the indices for which $a_{i_{t}}\neq 0$, $1\leq t\leq s$. Then define

 $g_{n}(x)=f_{i_{1}}(x)f_{i_{2}}(x)\cdots f_{i_{s}}(x)$

Thus, $g_{n}(x)$ evaluates to:

 $\displaystyle(x^{2^{i_{1}}})(x^{2^{i_{2}}})\cdots(x^{2^{i_{s}}})$ $\displaystyle=(x^{2^{0}})^{a_{0}}(x^{2^{1}})^{a_{1}}\cdots(x^{2^{k}})^{a_{k}}$ $\displaystyle=x^{a_{0}2^{0}+a_{1}2^{1}+\cdots+a_{k}2^{k}}$ $\displaystyle=x^{n}.$

Because each $f_{i+1}(x)$ uses the output of $f_{i}(x)$, the cost of evaluating $g_{n}$ is the cost of evaluating $f_{i_{s}}(x)$ plus the final cost of multiplying $f_{i_{1}}(x)\cdots f_{i_{s}}(x)$. Thus, evaluating $g_{n}$ uses $i_{s}+(s-1)$ multiplications. As $s\leq\log_{2}n$ it follows that evaluating $g_{n}$ uses no more than $2\log_{2}n$ multiplications. ∎

Title method of repeated squaring MethodOfRepeatedSquaring 2013-03-22 16:16:14 2013-03-22 16:16:14 Algeboy (12884) Algeboy (12884) 9 Algeboy (12884) Theorem msc 20A05 msc 08A99 msc 20-00 successive squaring