# 平方求幂

## 基本方法

${\displaystyle x^{n}={\begin{cases}x\,(x^{2})^{\frac {n-1}{2}},&{\mbox{if }}n{\mbox{ is odd}}\\(x^{2})^{\frac {n}{2}},&{\mbox{if }}n{\mbox{ is even}}.\end{cases}}}$

1. ${\displaystyle r\leftarrow r^{2}\,(=x^{0})}$，第1位 = 1，所以计算 ${\displaystyle r\leftarrow r\cdot x\,(=x^{1})}$
2. ${\displaystyle r\leftarrow r^{2}\,(=x^{2})}$，第2位 = 1，所以计算 ${\displaystyle r\leftarrow r\cdot x\,(=x^{3})}$
3. ${\displaystyle r\leftarrow r^{2}\,(=x^{6})}$，第3位 = 0，所以这一步什么都不做。
4. ${\displaystyle r\leftarrow r^{2}\,(=x^{12})}$，第4位 = 1，所以计算 ${\displaystyle r\leftarrow r\cdot x\,(=x^{13})}$

  Function exp_by_squaring(x, n)
if n < 0  then return exp_by_squaring(1 / x, -n);
else if n = 0  then return  1;
else if n = 1  then return  x ;
else if n is even  then return exp_by_squaring(x * x,  n / 2);
else if n is odd  then return x * exp_by_squaring(x * x, (n - 1) / 2);


  Function exp_by_squaring(x, n)
exp_by_squaring2(1, x, n)
Function exp_by_squaring2(y, x, n)
if n < 0  then return exp_by_squaring2(y, 1 / x, - n);
else if n = 0  then return  y;
else if n = 1  then return  x * y;
else if n is even  then return exp_by_squaring2(y, x * x,  n / 2);
else if n is odd  then return exp_by_squaring2(x * y, x * x, (n - 1) / 2).


  Function exp_by_squaring_iterative(x, n)
if n < 0 then
x := 1 / x;
n := -n;
if n = 0 then return 1
y := 1;
while n > 1 do
if n is even then
x := x * x;
n := n / 2;
else
y := x * y;
x := x * x;
n := (n – 1) / 2;
return x * y


c++实现（非递归） 返回${\displaystyle p^{n}}$${\displaystyle Mod}$求模

long long power(long long p, long long n)
{
long long ans = 1;
while (n)
{
if (n & 1) ans = (ans * p) % Mod;
p = p * p % Mod;
n >>= 1;
}
return ans;
}


## 计算复杂度

${\displaystyle \sum \limits _{i=0}^{O(\log(n))}(2^{i}O(\log(x)))^{k}=O((n\log(x))^{k})}$

## ${\displaystyle 2^{k}}$法

G 的一个元素 ${\displaystyle x}$，参数 ${\displaystyle k>0}$，一个非零整数 ${\displaystyle n=(n_{l-1},n_{l-2},\ldots n_{0})_{2}{^{k}}}$ 以及预计算的值 ${\displaystyle x^{3},x^{5},...,x^{2^{k}-1}}$

G 中的元素 ${\displaystyle x^{n}}$
y := 1; i := l-1
while i>=0 do
(s,u) := f(ni)
for j:=1 to k-s do
y := y2
y := y*xu
for j:=1 to s do
y := y2
i := i-1
return y


${\displaystyle \log(n)<{\frac {k(k+1)\cdot 2^{2k}}{2^{k+1}-k-2}}+1}$

## 滑动窗口法

G的元素 ${\displaystyle x}$，非负整数 ${\displaystyle n=(n_{l-1},n_{l-2},\ldots n_{0})_{2}}$，一个参数 ${\displaystyle k>0}$，以及预计算的值 ${\displaystyle x^{3},x^{5},...,x^{2^{k}-1}}$

y := 1; i := l-1
while i > -1 do
if ni=0 then
y:=y2' i:=i-1
else
s:=max{i-k+1,0}
while ns=0 do
s:=s+1 [notes 1]
for h:=1 to i-s+1 do
y:=y2
u:=(ni,ni-1,....,ns)2
y:=y*xu
i:=s-1
return y


## 蒙哥马利阶梯法

x1=x; x2=x2
for i=k-2 to 0 do
If ni=0 then
x2=x1*x2; x1=x12
else
x1=x1*x2; x2=x22
return x1


## 固定基底的幂

### 姚期智的方法

${\displaystyle n=\sum _{i=0}^{w-1}n_{i}b_{i}}$ 其中对所有 ${\displaystyle i\in [0,w-1]}$ 都有 ${\displaystyle 0\leqslant n_{i}

${\displaystyle x_{i}=x^{b_{i}}}$。该算法使用等式

${\displaystyle x^{n}=\prod _{i=0}^{w-1}{x_{i}}^{n_{i}}=\prod _{j=1}^{h-1}{{\bigg [}\prod _{n_{i}=j}x_{i}{\bigg ]}}^{j}}$

 y=1,u=1 and j=h-1
while j > 0 do
for i=0 to w-1 do
if ni=j then u=u*xbi
y=y*u
j=j-1
return y


### 欧几里得法

${\displaystyle {x_{0}}^{n_{0}}\cdot {x_{1}}^{n_{1}}={\left(x_{0}\cdot {x_{1}}^{q}\right)}^{n_{0}}\cdot {x_{1}}^{n_{1}\mod {n_{0}}}}$, where ${\displaystyle q=\left\lfloor {\frac {n_{1}}{n_{0}}}\right\rfloor }$
（换句话说，用指数 ${\displaystyle n_{1}}$${\displaystyle n_{0}}$ 的欧几里得除法来返回商 ${\displaystyle q}$ 和余数 ${\displaystyle n_{1}{\bmod {n}}_{0}}$）。

    Begin loop
Find ${\displaystyle M\in \left[0,l-1\right]}$, such that ${\displaystyle \forall i\in \left[0,l-1\right],{n_{M}}\geq {n_{i}}}$;
Find ${\displaystyle N\in \left(\left[0,l-1\right]-M\right)}$, such that ${\displaystyle \forall i\in \left(\left[0,l-1\right]-M\right),{n_{N}}\geq {n_{i}}}$;
Break loop if ${\displaystyle {n_{N}}=0}$;
Let ${\displaystyle q=\left\lfloor {n_{M}}/{n_{N}}\right\rfloor }$, and then let ${\displaystyle {n_{N}}=\left({n_{M}}{\bmod {n_{N}}}\right)}$;
Compute recursively ${\displaystyle {x_{M}}^{q}}$, and then let ${\displaystyle {x_{N}}={x_{N}}\cdot {x_{M}}^{q}}$;
End loop;
Return ${\displaystyle x^{n}={x_{M}}^{n_{M}}}$.


## 更多应用

Power(x, −n) = (Power(x, n))−1.

13789722341 (mod 2345)

## 示例实现

### 通过2的幂进行计算

def power(x,n)
result = 1
while n.nonzero?
if n[0].nonzero?
result *= x
n -= 1
end
x *= x
n /= 2
end
return result
end


#### 运行实例：计算 310

parameter x =  3
parameter n = 10
result := 1

Iteration 1
n = 10 -> n is even
x := x2 = 32 = 9
n := n / 2 = 5

Iteration 2
n = 5 -> n is odd
-> result := result * x = 1 * x = 1 * 32 = 9
n := n - 1 = 4
x := x2 = 92 = 34 = 81
n := n / 2 = 2

Iteration 3
n = 2 -> n is even
x := x2 = 812 = 38 = 6561
n := n / 2 = 1

Iteration 4
n = 1 -> n is odd
-> result := result * x = 32 * 38 = 310 = 9 * 6561 = 59049
n := n - 1 = 0

return result


#### 运行实例：计算 310

result := 3
bin := "1010"

Iteration for digit 2:
result := result2 = 32 = 9
1010bin - Digit equals "0"

Iteration for digit 3:
result := result2 = (32)2 = 34  = 81
1010bin - Digit equals "1" --> result := result*3 = (32)2*3 = 35  = 243

Iteration for digit 4:
result := result2 = ((32)2*3)2 = 310  = 59049
1010bin - Digit equals "0"

return result


JavaScript-Demonstration: http://home.mnet-online.de/wzwz.de/temp/ebs/en.htm页面存档备份，存于互联网档案馆

### 幂的乘积的计算

#### 例子

((a)2×a)2×a （计算 a7 需要四次乘法）
((b)2)2×b   （计算 b5 需要三次乘法）
(a7)×(b5) （计算二者乘积需要一次乘法）

((a×b)2×a)2×a×b

27×35 = ((2×3)2×2)2×2×3 = (62×2)2×6 = 722×6 = 31,104

#### 使用变换

a7×b5 = a2×(ab)5 其中 ab := a×b

ab := a×b（一次乘法）
a2×(ab)5 = ((ab)2×a)2×ab（四次乘法）

#### 例子

11次乘法）
[((a)2)2×a] × [((b)2)2×b] × [(c)2×c]
10次乘法）
[((a)2×a)2×a] × [((b)2)2] × [c]
8次乘法）

8次乘法）
((a×b)2×c)2×a×b×c
7次乘法）
((a×b)2×a)2×a×c
6次乘法）

（2次乘法）
a := 2   ab := a×b   abc := ab×c
（2次乘法）
a := 2   ab := a×b   abc := ab×c
（2次乘法）

（4次乘法 ⇒ 总共6次）
(ab×abc)2×abc
（3次乘法 ⇒ 总共5次）
(a×ab)2×a×ab×abc
（5次乘法 ⇒ 总共7次）

## 用有符号数字重新编码

${\displaystyle n=\sum _{i=0}^{l-1}n_{i}b^{i}{\text{ with }}|n_{i}|

${\displaystyle c_{0}=0}$
for i = 0 to l - 1 do
${\displaystyle c_{i+1}=\left\lfloor {\frac {1}{2}}(c_{i}+n_{i}+n_{i+1})\right\rfloor }$
${\displaystyle n_{i}'=c_{i}+n_{i}-2c_{i+1}}$
return ${\displaystyle (n_{l-1}'\dots n_{0}')_{\text{NAF}}}$


Koyama和Tsuruoka的另一种算法并不要求 ${\displaystyle n_{i}=n_{i+1}=0}$ 这样的条件；它仍然可以让汉明重量最小化。

## 替代方法及推广

${\displaystyle a^{15}=x\times (x\times [x\times x^{2}]^{2})^{2}\!}$ （平方求幂，6次乘法）
${\displaystyle a^{15}=x^{3}\times ([x^{3}]^{2})^{2}\!}$ （最优加法链，在复用 ${\displaystyle x^{3}}$ 的情况下只需要5次乘法）

## 注释

1. ^ In this line, the loop finds the longest string of length less than or equal to 'k' which ends in a non zero value. And not all odd powers of 2 up to ${\displaystyle x^{2^{k}-1}}$ need be computed and only those specifically involved in the computation need be considered.

## 参考文献

1. Cohen, H.; Frey, G. (编). Handbook of Elliptic and Hyperelliptic Curve Cryptography. Discrete Mathematics and Its Applications. Chapman & Hall/CRC. 2006. ISBN 9781584885184.
2. ^ Montgomery, Peter L. Speeding the Pollard and Elliptic Curve Methods of Factorization (PDF). Math. Comput. 1987, 48 (177): 243–264 [2018-02-17]. （原始内容存档 (PDF)于2018-01-27）.