查看“︁平方求幂”︁的源代码

{{NoteTA
|G1 = IT
}}
在[[数学]]和[[程序设计]]中，'''平方求冪'''（{{lang-en|exponentiating by squaring}}）或'''快速冪'''是快速计算一个数（或更一般地说，一个[[半群]]的元素，如[[多項式]]或[[方块矩阵|方阵]]）的大[[自然数|正整数]]乘[[幂]]的一般方法。这些算法可以非常通用，例如用在[[模算數]]或矩阵幂。对于通常使用[[阿贝尔群|加性表示法]]的半群，如[[密码学]]中使用的[[椭圆曲线]]，这种方法也称为'''double-and-add'''。

==基本方法==

该方法是基于观察到，对于正整数<math>n</math>，可知

:<math>
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}
</math>

该方法使用指数的位（二进制的位，即bit，下文称为“位”）来确定计算哪些幂。

此例显示如何使用此方法计算 <math>x^{13}</math>。
幂指数13的二进制为1101。这些位按照从左到右的顺序使用。
指数有4位，所以有4次迭代。

首先，将结果初始化为1：<math>r \leftarrow 1 \, ( = x^0)</math>
# <math>r \leftarrow r^2 \, ( = x^0)</math>，第1位 = 1，所以计算 <math>r \leftarrow r \cdot x \,( = x^1)</math>。
# <math>r \leftarrow r^2 \, ( = x^2)</math>，第2位 = 1，所以计算 <math>r \leftarrow r \cdot x \, ( = x^3)</math>。
# <math>r \leftarrow r^2 \, ( = x^6)</math>，第3位 = 0，所以这一步什么都不做。
# <math>r \leftarrow r^2 \, ( = x^{12})</math>，第4位 = 1，所以计算 <math>r \leftarrow r \cdot x \, ( = x^{13})</math>。

这可以按照下面的[[递归 (计算机科学)|递归算法]]来实现：
<syntaxhighlight lang="pascal">
  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);
</syntaxhighlight>

尽管不是[[尾调用]]，但是通过引入辅助函数，该算法可以被重写成尾递归算法：

<syntaxhighlight lang="pascal">
  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).
</syntaxhighlight>

该算法的迭代版本的辅助空间是有界的，代码如下

<syntaxhighlight lang="pascal">
  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
</syntaxhighlight>

c++实现（非递归）
返回<math>p^n</math> 对<math>Mod</math>求模
<syntaxhighlight lang="c++">
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;
}
</syntaxhighlight>

==计算复杂度==

简要分析表明此算法用了 <math>\lfloor \log_2n\rfloor</math> 次平方，以及至多 <math>\lfloor \log_2n\rfloor</math> 次乘法，其中 <math>\lfloor\;\rfloor</math> 表示[[高斯符號|向下取整函数]]。更确切地说，做乘法的次数比 <math>n</math> 的[[二进制|二进制展开]]的次数要少一次。对于 <math>n</math> 大于4左右的时候，这种算法在计算上就已经比''天真地''将它与自身重复地相乘更高效了。

每次平方的结果大约是前一次结果的两倍，因此，如果两个 <math>d</math> 位数的相乘的实现要进行 <math>\mathrm{O}(d^k)</math> 次计算（其中 <math>k</math> 为一固定值），那么计算 <math>x^n</math> 的复杂度为：

:<math> \sum\limits_{i=0}^{O(\log(n))} (2^i O(\log(x)))^k = O((n \log(x))^k)  
</math>

==<math>2^k</math>法==
此算法先把指数展开成 <math>2^k</math> 形式，然后再计算 <math>x^n</math> 的值。它在1939年由[[Brauer]]首次提出。在下面的算法中，使用以下函数 <math>f(0) = (k,0)</math> 和<math>f(m) = (s,u)</math>，其中 <math>m = u\cdot 2^s</math>，<math>u</math> 为奇数。

算法：

;输入: G 的一个元素 <math>x</math>，参数 <math>k>0</math>，一个非零整数 <math>n=(n_{l-1}, n_{l-2}, \ldots n_0)_2{^k}</math> 以及预计算的值 <math style="vertical-align:baseline;">x^3, x^5, ... , x^{2^k-1}</math>。

;输出: ''G'' 中的元素 <math>x^n</math>

 y := 1; i := l-1
 '''while''' i>=0 do
     (s,u) := f(n<sub>i</sub>)
     '''for''' j:=1 '''to''' k-s '''do'''
         y := y<sup>2</sup> 
     y := y*x<sup>u</sup>
     '''for''' j:=1 '''to''' s '''do'''
         y := y<sup>2</sup>
     i := i-1
 '''return''' y

为了获得最佳效率，''<math>k</math>'' 应该是满足

:<math>\log(n) < \frac{k(k+1) \cdot 2^{2k}}{2^{k+1} - k - 2} + 1</math>

的最小整数。<ref name="frey">{{cite book |editor1-last=Cohen |editor1-first=H. |editor2-last=Frey, G. |date=2006 |title=Handbook of Elliptic and Hyperelliptic Curve Cryptography |series=Discrete Mathematics and Its Applications |publisher=Chapman & Hall/CRC |isbn=9781584885184}}</ref>

==滑动窗口法==
此方法是 <math>2^k</math> 法的更高效的变体。例如，要计算398次幂，二进制展开为 (110 001 110)<sub>2</sub>，采用长度为3的窗，使用 <math>2^k</math> 法，需要计算 1, <math>x^3, x^6, x^{12}, x^{24}, x^{48}, x^{49}, x^{98}, x^{99}, x^{198}, x^{199}, x^{398}</math>。
但也可以计算 1,<math>x^3, x^6, x^{12}, x^{24}, x^{48}, x^{49}, x^{96}, x^{192}, x^{198}, x^{199}, x^{398}</math>，这就会省下一次乘法，相当于是计算 (110 001 110)n<sub>2</sub> 的值

以下是一般算法：

算法：

;输入: ''G''的元素 ''<math>x</math>''，非负整数 <math>n=(n_{l-1}, n_{l-2}, \ldots n_0)_2</math>，一个参数 <math>k>0</math>，以及预计算的值 <math style="vertical-align:baseline;">x^3, x^5, ... ,x^{2^k-1}</math>。

;输出: 元素 <math>x^n\in G</math>

算法：

 y := 1; i := l-1
 '''while''' i > -1 '''do'''
     '''if''' n<sub>i</sub>=0 '''then'''
         y:=y<sup>2</sup>' i:=i-1
     '''else'''
         s:=max{i-k+1,0}
         '''while''' n<sub>s</sub>=0 '''do'''
             s:=s+1 <ref group=notes>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 <math style="vertical-align:baseline;">x^{2^k-1}</math> need be computed and only those specifically involved in the computation need be considered.</ref>
         '''for''' h:=1 '''to''' i-s+1 '''do'''
             y:=y<sup>2</sup>
         u:=(n<sub>i</sub>,n<sub>i-1</sub>,....,n<sub>s</sub>)<sub>2</sub>
         y:=y*x<sup>u</sup>
         i:=s-1
 '''return''' y

==蒙哥马利阶梯法==
求幂的许多算法都不提供对[[旁路攻击]]的防护。也就是说，监测到乘方运算的攻击者可以（部分）还原所计算的指数。就如众多[[公开密钥加密|公钥加密系统]]中那样，如果指数需要保密的话，这就是个问题了。一个叫做[[Peter Montgomery (mathematician)|蒙哥马利阶梯]]<ref name="ladder">{{cite journal |last=Montgomery |first=Peter L. |date=1987 |title=Speeding the Pollard and Elliptic Curve Methods of Factorization |journal=Math. Comput. |volume=48 |number=177 |pages=243–264 |url=http://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866113-7/S0025-5718-1987-0866113-7.pdf |format=PDF |access-date=2018-02-17 |archive-date=2018-01-27 |archive-url=https://web.archive.org/web/20180127182929/http://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866113-7/S0025-5718-1987-0866113-7.pdf |dead-url=no }}</ref>的方法解决了这个问题。 

给定一个非零正整数的[[二进制|二进制展开]] <math>n=(n_{k-1}\ldots n_0)_2</math>（其中 <math>n_{k-1}=1</math>），可以以下面方式计算 <math>x^n</math>：
 x<sub>1</sub>=x; x<sub>2</sub>=x<sup>2</sup>
 for i=k-2 to 0 do
   If n<sub>i</sub>=0 then
     x<sub>2</sub>=x<sub>1</sub>*x<sub>2</sub>; x<sub>1</sub>=x<sub>1</sub><sup>2</sup>
   else
     x<sub>1</sub>=x<sub>1</sub>*x<sub>2</sub>; x<sub>2</sub>=x<sub>2</sub><sup>2</sup>
 return x<sub>1</sub>

该算法会执行一系列固定的操作（复杂度<math>\log n</math>）：无论每一位的具体值如何，指数中的每一位都会进行乘法和平方。

蒙哥马利阶梯法的这种具体实现还无法抵御缓存{{le|时序攻击|timing attack}}：当根据秘密指数的位值访问不同的变量时，内存访问延迟仍可能被攻击者观察到。

==固定基底的幂==
当基底固定而指数变化时，可以使用几种方法来计算 <math>x^n</math>。可以看出，预计算在这些算法中起着关键作用。

===姚期智的方法===
姚期智的方法与 <math>2^k</math> 法不同，是把指数以 <math>b=2^k</math> 为基底展开，并按上面的算法进行计算。令 <math>n</math>, <math>n_i</math>, <math>b</math>, <math>b_i</math> 为整数。

把指数 <math>n</math> 写成
:<math> n = \sum_{i=0}^{w-1} n_ib_i</math> 其中对所有 <math>i \in [0,w-1] </math> 都有 <math> 0 \leqslant n_i < h</math>

令 <math>x_i=x^{b_i}</math>。该算法使用等式
:<math> 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 </math>

给定 <math>G</math> 的元素 <math>x</math>，指数 <math>n</math> 写成上述形式，并且预先计算 <math>x^{b_0}\ldots x^{b_{w-1}}</math> 的值，元素 <math>x^n</math> 就可以用下面的算法计算了。

  y=1,u=1 and j=h-1
  while j > 0 do
    for i=0 to w-1 do
      if n<sub>i</sub>=j then u=u*x<sup>b<sub>i</sub></sup>
    y=y*u
    j=j-1
  return y

如果令 <math>h=2^k</math>，<math>b_i=h^i</math>，那么这些 <math>n_i</math> 就是 <math>n</math>  以 <math>h</math> 为基的每一位。姚期智的方法是把之前的那些 <math>x_i</math> 收集到 <math>u</math> 中，which appear to the highest power {{tmath|h-1}}；in the next round those with power {{tmath|h-2}} are collected in <math>u</math> as well etc. 变量 <math>y</math> 被原始的 <math>u</math> 乘了 {{tmath|h-1}} 次，内第二高的指数乘了 {{tmath|h-2}} 次……
该算法计算 <math>x^n</math> 要用 {{tmath|w+h-2}} 次乘法，存储 {{tmath|w+1}} 个元素。<ref name=frey />

===欧几里得法===
欧几里德法首先在P.D Rooij的《使用预计算和向量加法链的高效求幂》（{{lang|en|Efficient exponentiation using precomputation and vector addition chains}}）中介绍。

这种计算群 {{math|'''G'''}} 中 <math>x^n</math>（<math>n</math> 为自然数）的方法是，递归地使用下面的等式：
: <math>{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}}</math>, where <math>q = \left\lfloor \frac {n_1} {n_0} \right\rfloor</math>
: （换句话说，用指数 <math>n_1</math> 与 <math>n_0</math> 的欧几里得除法来返回商 <math>q</math> 和余数 <math>n_1 \bmod n_0</math>）。

给定群 {{math|'''G'''}} 中的基底元素 <math>x</math>，把指数 <math>n</math> 用姚期智的方法写出来，然后就可以用预计算的 <math>l</math> 个值 <math>x^{b_0}, ..., x^{b_{l_i}}</math> 计算 <math>x^n</math> 了。

     '''Begin loop'''   
         {{nowrap|Find <math>M \in \left[ 0, l - 1 \right]</math>,}} {{nowrap|such that <math>\forall i \in \left[ 0, l - 1 \right], {n_M} \ge {n_i}</math>;}}
         {{nowrap|Find <math>N \in \left( \left[ 0, l - 1 \right] - M \right)</math>,}} {{nowrap|such that <math>\forall i \in \left( \left[ 0, l - 1 \right] - M \right), {n_N} \ge {n_i}</math>;}}
         '''Break loop''' {{nowrap|if <math>{n_N} = 0</math>;}}
         {{nowrap|'''Let''' <math>q = \left\lfloor {n_M} / {n_N} \right\rfloor</math>,}} {{nowrap|and then '''let''' <math>{n_N} = \left( {n_M} \bmod {n_N} \right)</math>;}}
         {{nowrap|Compute recursively <math>{x_M}^q</math>,}} {{nowrap|and then '''let''' <math>{x_N} = {x_N} \cdot {x_M}^q</math>;}}
     '''End loop''';
     {{nowrap|'''Return''' <math>x^n = {x_M}^{n_M}</math>.}}

该算法首先在 <math>n_i</math> 中找到最大值，在找到集合 <math>\{n_i \backslash i\neq M\}</math> 中的最大值。
然后递归求 <math>x_M</math> 的 <math>q</math> 次幂，把这个值乘以 <math>x_N</math>，赋值给 <math>x_N</math>；把 <math>n_M</math> 模 <math>n_N</math> 的结果赋值给 <math>n_M</math>。

==更多应用==
这一思路还可用于计算大[[Modular exponentiation|指数幂除以一个数的余数]]。特别是在[[密码学]]中，在[[模算數|整数除以''q''的余数]]的[[环 (代数)|环]]中计算幂是很有用处的。在[[群]]中计算整数幂也是很有用的，使用法则

:Power(''x'', −''n'') = (Power(''x'', ''n''))<sup>−1</sup>.

该方法对所有[[半群]]都适用，通常用于计算[[矩阵]]的幂。

例如，如果使用朴素的方法，计算

:13789<sup>722341</sup> (mod 2345)

将花费很长时间以及大量的存储空间：计算 13789<sup>722341</sup>，并除以2345求[[余数|余]]。即便使用更有效的方法也需要很长时间：求13789的平方，除以2345求余，将结果乘以13789，再求余，一直往下计算。这会需要 <math>2\log_2(722340)\leq 40</math> 次模乘。

把“*”理解为 ''x''*''y'' = ''xy'' mod 2345（即相乘后取模）后，应用上面的平方求幂算法，只需要27次乘法和整数除法（所有这些都可以存储在单个机器字中）就可以完成计算了。

==示例实现==

===通过2的幂进行计算===
这是用[[Ruby]]写的上述算法的非递归实现。

由于低级语言会将 n=n/2 隐式向0取整，n=n-1 对那些语言来说，就是冗余的步骤了。
n[0]是n的二进制表示的最右边的位，所以如果它是1，则该数是奇数，如果它是零，则该数是偶数。它也是以2为模n的余数。

<syntaxhighlight lang="ruby">
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
</syntaxhighlight>

====运行实例：计算 3<sup>10</sup>====
 parameter x =  3
 parameter n = 10
 result := 1
 
 '''Iteration 1'''
   n = 10 -&gt; n is even
   x := x<sup>2</sup> = 3<sup>2</sup> = 9
   n := n / 2 = 5
 
 '''Iteration 2'''
   n = 5 -&gt; n is odd
       -&gt; result := result * x = 1 * x = 1 * 3<sup>2</sup> = 9
          n := n - 1 = 4
   x := x<sup>2</sup> = 9<sup>2</sup> = 3<sup>4</sup> = 81
   n := n / 2 = 2
 
 '''Iteration 3'''
   n = 2 -&gt; n is even
   x := x<sup>2</sup> = 81<sup>2</sup> = 3<sup>8</sup> = 6561
   n := n / 2 = 1
 
 '''Iteration 4'''
   n = 1 -&gt; n is odd
       -&gt; result := result * x = 3<sup>2</sup> * 3<sup>8</sup> = 3<sup>10</sup> = 9 * 6561 = 59049
          n := n - 1 = 0
 
 return result

====运行实例：计算 3<sup>10</sup>====
 result := 3
 bin := "1010"
 
 '''Iteration for digit 2:'''
   result := result<sup>2</sup> = 3<sup>2</sup> = 9
   1'''0'''10<sub>bin</sub> - Digit equals "0"
 
 '''Iteration for digit 3:'''
   result := result<sup>2</sup> = (3<sup>2</sup>)<sup>2</sup> = 3<sup>4</sup>  = 81
   10'''1'''0<sub>bin</sub> - Digit equals "1" --&gt;&nbsp;result := result*3 = (3<sup>2</sup>)<sup>2</sup>*3 = 3<sup>5</sup>  = 243
 
 '''Iteration for digit 4:'''
   result := result<sup>2</sup> = ((3<sup>2</sup>)<sup>2</sup>*3)<sup>2</sup> = 3<sup>10</sup>  = 59049
   101'''0'''<sub>bin</sub> - Digit equals "0"
 
 return result

JavaScript-Demonstration: http://home.mnet-online.de/wzwz.de/temp/ebs/en.htm {{Wayback|url=http://home.mnet-online.de/wzwz.de/temp/ebs/en.htm |date=20170331053757 }}

===幂的乘积的计算===
平方求幂也可用于计算2个或多个幂的乘积。
如果基础群或半群是[[交換律|可交换]]的，那么常常可以通过同时计算乘积来减少乘法的次数。

====例子====
式子 a<sup>7</sup>×b<sup>5</sup> 可以分三步计算：
:((a)<span style="color:red;"><sup>2</sup>×</span>a)<span style="color:red;"><sup>2</sup>×</span>a  （计算 a<sup>7</sup> 需要四次乘法）
:((b)<span style="color:red;"><sup>2</sup></span>)<span style="color:red;"><sup>2</sup>×</span>b    （计算 b<sup>5</sup> 需要三次乘法）
: (a<sup>7</sup>)<span style="color:red;">×</span>(b<sup>5</sup>) （计算二者乘积需要一次乘法）
所以总共需要八次乘法。

更快的解法是同时计算这两个幂
:((a<span style="color:red;">×</span>b)<span style="color:red;"><sup>2</sup>×</span>a)<span style="color:red;"><sup>2</sup>×</span>a<span style="color:red;">×</span>b
总共只需要6次乘法。注意 a×b 计算了两次；结果可以在第一次计算后存储，这将乘法计数减少到5次。

有数字的例子：
:2<sup>7</sup>×3<sup>5</sup>&nbsp;=&nbsp;((2×3)<sup>2</sup>×2)<sup>2</sup>×2×3&nbsp;=&nbsp;(6<sup>2</sup>×2)<sup>2</sup>×6&nbsp;=&nbsp;72<sup>2</sup>×6&nbsp;=&nbsp;31,104

如果至少有两个指数大于1的话，同时计算幂就会比单独计算减少乘法次数。

====使用变换====
如果表达式在计算前进行变换，上面的例子 a<sup>7</sup>×b<sup>5</sup> 也可以只用5次乘法就计算出来：

a<sup>7</sup>×b<sup>5</sup> = a<sup>2</sup>×(ab)<sup>5</sup> 其中 ab := a×b
<dl>
<dd>ab := a<span style="color:red;">×</span>b（一次乘法）</dd>
<dd>a<sup>2</sup>×(ab)<sup>5</sup> = ((ab)<span style="color:red;"><sup>2</sup>×</span>a)<span style="color:red;"><sup>2</sup>×</span>ab（四次乘法）</dd>
</dl>

这个变换可以推广成下面的方案：<br>
对于计算 a<sup>A</sup>×b<sup>B</sup>×...×m<sup>M</sup>×n<sup>N</sup><br>
首先：定义 ab := a×b, abc = ab×c, ...<br>
然后：计算变换后的表达式 a<sup>A−B</sup>×ab<sup>B−C</sup>×...×abc..m<sup>M−N</sup>×abc..mn<sup>N</sup>

在计算之前进行变换通常会减少乘法计数，但在某些情况下也会增加计数（请参见下面最后一个示例），因此在使用变换后的表达式进行计算之前，最好检查一下乘法的次数。

====例子====
对于下面的表达式，表中显示了分开计算每个幂，在不进行变换的情况下同时进行计算，以及在变换后同时进行计算的乘法次数。
{|class="wikitable"
!例子
! a<sup>7</sup>×b<sup>5</sup>×c<sup>3</sup>
! a<sup>5</sup>×b<sup>5</sup>×c<sup>3</sup>
! a<sup>7</sup>×b<sup>4</sup>×c<sup>1</sup>
|-
!分开计算
| [((a)<span style="color:red;"><sup>2</sup>×</span>a)<span style="color:red;"><sup>2</sup>×</span>a] <span style="color:red;">×</span> [((b)<span style="color:red;"><sup>2</sup></span>)<span style="color:red;"><sup>2</sup>×</span>b] <span style="color:red;">×</span> [(c)<span style="color:red;"><sup>2</sup>×</span>c]<br/>（'''11'''次乘法）
| [((a)<span style="color:red;"><sup>2</sup></span>)<span style="color:red;"><sup>2</sup>×</span>a] <span style="color:red;">×</span> [((b)<span style="color:red;"><sup>2</sup></span>)<span style="color:red;"><sup>2</sup>×</span>b] <span style="color:red;">×</span> [(c)<span style="color:red;"><sup>2</sup>×</span>c]<br/>（'''10'''次乘法）
| [((a)<span style="color:red;"><sup>2</sup>×</span>a)<span style="color:red;"><sup>2</sup>×</span>a] <span style="color:red;">×</span> [((b)<span style="color:red;"><sup>2</sup></span>)<span style="color:red;"><sup>2</sup></span>] <span style="color:red;">×</span> [c]<br/>（'''8'''次乘法）
|-
!同时计算
| ((a<span style="color:red;">×</span>b)<span style="color:red;"><sup>2</sup>×</span>a<span style="color:red;">×</span>c)<span style="color:red;"><sup>2</sup>×</span>a<span style="color:red;">×</span>b<span style="color:red;">×</span>c<br/>（'''8'''次乘法）
| ((a<span style="color:red;">×</span>b)<span style="color:red;"><sup>2</sup>×</span>c)<span style="color:red;"><sup>2</sup>×</span>a<span style="color:red;">×</span>b<span style="color:red;">×</span>c<br/>（'''7'''次乘法）
| ((a<span style="color:red;">×</span>b)<span style="color:red;"><sup>2</sup>×</span>a)<span style="color:red;"><sup>2</sup>×</span>a<span style="color:red;">×</span>c<br/>（'''6'''次乘法）
|-
!变换
| a := 2 &nbsp; ab := a<span style="color:red;">×</span>b &nbsp; abc := ab<span style="color:red;">×</span>c<br/>（2次乘法）
| a := 2 &nbsp; ab := a<span style="color:red;">×</span>b &nbsp; abc := ab<span style="color:red;">×</span>c<br/>（2次乘法）
| a := 2 &nbsp; ab := a<span style="color:red;">×</span>b &nbsp; abc := ab<span style="color:red;">×</span>c<br/>（2次乘法）
|-
!之后的计算 
| (a<span style="color:red;">×</span>ab<span style="color:red;">×</span>abc)<span style="color:red;"><sup>2</sup>×</span>abc<br/>（4次乘法 ⇒ 总共'''6'''次）
| (ab<span style="color:red;">×</span>abc)<span style="color:red;"><sup>2</sup>×</span>abc<br/>（3次乘法 ⇒ 总共'''5'''次）
| (a<span style="color:red;">×</span>ab)<span style="color:red;"><sup>2</sup>×</span>a<span style="color:red;">×</span>ab<span style="color:red;">×</span>abc<br/>（5次乘法 ⇒ 总共'''7'''次）
|}

==用有符号数字重新编码==
在某些计算中，如果允许负系数（也就会需要用基底的倒数）的话，只要在 <math>\boldsymbol{G}</math> 中计算倒数很快或者已经预先计算，求幂会更加高效。例如，当计算 <math>x^{2^k-1}</math> 时，二进制方法需要 <math>k-1</math> 次乘法和 <math>k-1</math> 次平方。不过可以用 <math>k</math> 次平方得到 <math>x^{2^k}</math>，然后乘以 <math>x^{-1}</math> 得到 <math>x^{2^k-1}</math>。

为此，定义以 <math>b</math> 为基数的整数 <math>n</math> 的{{le|有符号数字表示|signed-digit representation}}为
:<math>n=\sum_{i=0}^{l-1}n_ib^i \text{  with  } |n_i|<b</math>

''有符号二进制表示''也就是选取 <math>b=2</math>，<math>n_i \in \{-1,0,1\}</math> 的表示法。记为 <math>(n_{l-1}\dots n_0)_s</math>。有多种计算这种表示的方法。该表示不是唯一的，例如，取 <math>n=478</math>。<math>(10\bar 1 1100\bar 1 10)_s</math> 和 <math>(100\bar 1 1000\bar 1 0)_s</math> 给出了两个不同的有符号二进制表示，其中 <math>\bar 1</math> 表示 -1。由于在二进制方法中，<math>n</math> 的基2表示的每个非零项都要计算乘法，因此感兴趣的是找到非零项数量最少的有符号二进制表示，即具有''最小''[[汉明重量]]的表示。有一种方法是计算{{le|非相邻形式|non-adjacent form}}（简称NAF）的有符号二进制表示，它满足对所有 <math>i\geqslant 0</math>，<math>n_in_{i+1}=0</math>，记为 <math>(n_{l-1}\dots n_0)_{\text{NAF}}</math>。例如，478的NAF表示为 <math>(1000\bar 1 000\bar 1 0)_{\text{NAF}}</math>。这种表示总是有最小的汉明重量。下面的简单算法可以计算 <math>n_l=n_{l-1}=0</math> 的整数 <math>n=(n_ln_{l-1}\dots n_0)_2</math> 的NAF表示：

 {{nowrap|<math>c_0=0</math>}}
 for {{math|1=''i'' = 0}} to {{math|''l'' - 1}} do
   {{nowrap|<math>c_{i+1}=\left\lfloor\frac{1}{2}(c_i+n_i+n_{i+1})\right\rfloor</math>}}
   {{nowrap|<math>n_i'=c_i+n_i-2c_{i+1}</math>}}
 {{nowrap|return <math>(n_{l-1}'\dots n_0')_{\text{NAF}}</math>}}

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

==替代方法及推广==
{{main|加法链求幂}}
平方求幂可以看作是一个次优的{{le|加法链求幂|addition-chain exponentiation}}算法：它通过由重复指数加倍（平方）和指数递增（乘以 <math>x</math>）组成的[[加法链]]来计算指数。更一般地，如果允许''任何''先前计算的指数相加（通过乘以 ''<math>x</math>'' 的幂），有时可以让求幂运算的乘法次数更少（但通常使用更多的内存）。<math>n=15</math> 时的最少次数：

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

一般来说，求给定指数的最佳加法链是一个难题，因为没有已知的高效算法，所以最优链通常只用于小指数（比如，在[[編譯器]]中已经预先存储了小指数幂的最佳链）。不过，有一些[[启发式搜索|启发式]]算法，虽然不是最优的，但是由于额外的簿记工作和内存使用量的增加而导致的乘法次数少于平方求幂。无论如何，乘法的次数永远不会比 [[大O符号|&Theta;]](log ''n'') 增长得更慢，所以这些算法只能减小平方求幂的渐进复杂度的常数因子。

==参见==
*[[模幂运算]]
*{{le|向量加法链|Vectorial addition chain}}
*[[蒙哥马利算法]]
*{{le|非相邻形式|Non-adjacent form}}
*[[加法链]]

==注释==
{{Reflist|group=notes}}

==参考文献==
{{Reflist}}

[[Category:指数]]
[[Category:计算机算术算法]]