平方求幂

在数学和程序设计中，平方求幂（英语：exponentiating by squaring）或快速幂是快速计算一个数（或更一般地说，一个半群的元素，如多项式或方阵）的大正整数幂的一般方法。这些算法可以非常通用，例如用在模算数或矩阵幂。对于通常使用加性表示法的半群，如密码学中使用的椭圆曲线，这种方法也称为double-and-add。

蒙哥马利阶梯法

求幂的许多算法都不提供对旁路攻击的防护。也就是说，监测到乘方运算的攻击者可以（部分）还原所计算的指数。就如众多公钥加密系统中那样，如果指数需要保密的话，这就是个问题了。一个叫做蒙哥马利阶梯的方法解决了这个问题。 
给定一个非零正整数的二进制展开 n=(nₖ₋₁...n₀)₂（其中 nₖ₋₁=1），我们可以以下面方式计算xⁿ：
x₁=x; x₂=x²
for i=k-2 to 0 do
  If nᵢ=0 then
    x₂=x₁*x₂; x₁=x₁²
  else
    x₁=x₁*x₂; x₂=x₂²
return x₁
该算法会执行一系列固定的操作（复杂度log n）：无论每一位的具体值如何，指数中的每一位都会进行乘法和平方。
蒙哥马利阶梯法的这种具体实现还无法抵御缓存时序攻击：当根据秘密指数的位值访问不同的变量时，内存访问延迟仍可能被攻击者观察到。

固定基底的幂

当基底固定而指数变化时，可以使用几种方法来计算xⁿ。可以看出，预计算在这些算法中起着关键作用。

通过2的幂进行计算

这是用Ruby写的上述算法的非递归实现。
由于低级语言会将n=n/2 隐式向0取整，n=n-1 对那些语言来说，就是冗余的步骤了。
n[0]是n的二进制表示的最右边的位，所以如果它是1，则该数是奇数，如果它是零，则该数是偶数。它也是以2为模n的余数。
def power(x,n)
  result = 1
  while n.nonzero?
    if n[0].nonzero?
      result *= x
      n -= 1
    end
    x *= x
    n /= 2
  end
  return resultend

运行实例：计算 310

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

Iteration 1
  n = 10 -> n is even
  x := x² = 3² = 9
  n := n / 2 = 5

Iteration 2
  n = 5 -> n is odd
      -> result := result * x = 1 * x = 1 * 3² = 9
         n := n - 1 = 4
  x := x² = 9² = 3⁴ = 81
  n := n / 2 = 2

Iteration 3
  n = 2 -> n is even
  x := x² = 81² = 3⁸ = 6561
  n := n / 2 = 1

Iteration 4
  n = 1 -> n is odd
      -> result := result * x = 3² * 3⁸ = 3¹⁰ = 9 * 6561 = 59049
         n := n - 1 = 0

return result

运行实例：计算 310

result := 3
bin := "1010"

Iteration for digit 2:
  result := result² = 3² = 9
  1010bin - Digit equals "0"

Iteration for digit 3:
  result := result² = (3²)² = 3⁴  = 81
  1010bin - Digit equals "1" --> result := result*3 = (3²)²*3 = 3⁵  = 243

Iteration for digit 4:
  result := result² = ((3²)²*3)² = 3¹⁰  = 59049
  1010bin - Digit equals "0"

return result
JavaScript-Demonstration: http://home.mnet-online.de/wzwz.de/temp/ebs/en.htm

幂的乘积的计算

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