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 ofcomputational 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 werecognize 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 thatwe do not define these functions with exponents because we wantto demonstrate that from an algorithm to multiply we can createan efficient algorithm to exponentiate.

For $1<i\\leq k$ define (recalling that $f_{i+1}$ may use the outputof 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<k\\leq\\log_{2}n$ . Let $0\\leq i_{1}<i_{2}<\\cdots<i_{s}\\leq k$ bethe indices for which $a_{i_{t}}\eq 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 ofevaluating $g_{n}$ is the cost of evaluating $f_{i_{s}}(x)$ plus the finalcost 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 thatevaluating $g_{n}$ uses no more than $2\\log_{2}n$ multiplications.∎