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<i\leq k$ 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<k\leq\log_{2}n$ . Let $0\leq i_{1}<i_{2}<\cdots<i_{s}\leq k$ 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
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