问题及解答

证明 $X^{62}$ 可以只用 8 次乘法算出.

当然, $X^{62}$ 可以用 9 次乘法算出.

\[
\begin{aligned}
X^{62}&=X^{31}\cdot X^{31}\\
X^{31}&=X^{15}\cdot X^{15}\cdot X\\
X^{15}&=X^{7}\cdot X^{7}\cdot X\\
X^{7}&=X^{3}\cdot X^{3}\cdot X\\
X^{3}&=X^{1}\cdot X^{1}\cdot X\\
\end{aligned}
\]

由 $x$ 生成 $x^2$, $x^4$, $x^8$ 用了三次乘法.

令 $y=x^4\cdot x^8$,  用了一次乘法.

由 $y$ 生成 $y^2$, $y^4$ 用了两次乘法.

最后

\[
x^{62}=y^{4}\cdot x^2\cdot y
\]

再用 2 次乘法. 总共用了8次.