简介

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

基本方法

该方法是基于观察到，对于正整数n，我们有

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

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

首先，将结果初始化为1：

，第1位 = 1，所以计算。

，第2位 = 1，所以计算。

，第3位 = 0，所以这一步我们什么都不做。

，第4位 = 1，所以计算。

替代方法及推广

主条目：加法链求幂

平方求幂可以看作是一个次优的加法链求幂算法：它通过由重复指数加倍（平方）和指数递增（乘以x）组成的加法链来计算指数。更一般地，如果允许任何先前计算的指数相加（通过乘以x的幂），有时可以让求幂运算的乘法次数更少（但通常使用更多的内存）。n=15 时的最少次数：

（平方求幂，6次乘法）

（最优加法链，在复用x的情况下只需要5次乘法）

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

参见