平方求幂

在数学和计算机编程中，平方取幂是快速计算一个数的大正整数幂的通用方法，或者更一般地计算半群的元素，如多项式或方阵。 一些变体通常称为平方和乘法算法或二进制取幂。 这些可以非常普遍地使用，例如在模算术或矩阵的幂中。 对于通常使用加法表示法的半群，如密码学中使用的椭圆曲线，这种方法也称为加法。

该方法基于以下观察：对于正整数 n

这可以直接实现为以下递归算法：

函数 exp_by_squaring(x, n) 如果 n <; 0 然后返回 exp_by_squaring(1 / x, -n); 否则，如果 n = 0，则返回 1； 否则如果 n 是偶数则返回 exp_by_squaring(x * x, n / 2); 否则如果 n 是奇数则返回 x * exp_by_squaring(x * x, (n – 1) / 2);

在每次递归调用中，n 的二进制表示的最低有效位被删除。 所以这个算法计算这个平方数和一个较低的乘法数，它等于 n 的二进制表示中 1 的个数。 该对数运算将与需要 n − 1 次乘法的普通算法进行比较。

该算法不是尾递归的。 这意味着它需要一个辅助内存，该内存与递归调用的数量大致成比例（或者更高，如果考虑到数据量的增加）。

下一节的算法使用不同的方法，生成的算法需要相同数量的操作，但使用与存储结果所需的内存大致相同的辅助内存。

如果递归地应用这个公式，从 y = 1 开始，最终得到一个等于 0 的指数，然后期望的结果就是左因子。

该算法的迭代版本也使用有界辅助空间

算法的正确性源于 y x n  在计算过程中是不变的；

这些算法使用的运算次数与上一节的算法完全相同，但乘法运算的顺序不同。

更准确地说，乘法的次数比 n 的二进制展开式中的乘法次数少 1。 对于大于约 4 的 n，这在计算上比天真地将基数与自身重复相乘更有效。

每个平方的结果大约是前一个数字的两倍。