平方-乘算法

我们如何计算像 $3^{50,000,000,000} \pmod{N}$ 这样的巨大幂次，而无需等到宇宙终结？这是支撑我们数字安全的核心问题，从加密消息到安全的在线交易无不如此。重复相乘的暴力方法在计算上是不可能的，然而这类计算每天都在瞬息之间发生数百万次。这个明显的悖论指向了一种更优雅、更强大的解决方案，它位于现代计算的核心。

本文将揭开实现这一切的方法的神秘面纱：平方-乘算法。在第一节“原理与机制”中，我们将剖析该算法，揭示它如何巧妙地利用指数的二进制表示，将一项不可能的任务转化为几个简单的步骤。我们将探索其逻辑基础，并量化其惊人的效率。随后，在“应用与跨学科联系”一节中，我们将看到这一计算原理如何作为一种通用工具，不仅促成了现代密码学，还解决了数论、图论和抽象代数中的问题。

想象一下，你被要求计算 $3^{21}$ 除以 $25$ 的余数。一种直接但略显繁琐的方法是计算 $3 \times 3 = 9$，然后 $9 \times 3 = 27$，即 $2 \pmod{25}$，接着 $2 \times 3 = 6$，如此反复二十次。现在，想象任务是计算 $3^{50,000,000,000} \pmod{N}$。如果你在一台每秒能进行十亿次乘法的超级计算机上开始这项计算，那么在太阳变成红巨星之后很久，你的曾曾曾……曾孙们仍在等待答案。暴力方法，即把这个数与自身相乘数十亿次，是一座计算量巨大到几乎无法攀登的高山。

而这正是我们电脑和手机内部不断进行的运算，构成了现代密码学的支柱。显然，一定有一条更聪明的登山之路。

找到这条路的秘诀在于一个简单而深刻的真理，这是你在小学就学过的：任何数字都可以用二进制书写，即写成 2 的幂之和。对于我们的小例子，指数 $21$ 就是 $16 + 4 + 1$。这就是它的​​二进制表示​​，我们可以写作 $(10101)_2$，其中从右到左“1”的位置对应着 $2^0=1$、$2^2=4$ 和 $2^4=16$ 这些幂。

指数的这种分解为我们的幂运算问题提供了一份蓝图。指数定律告诉我们 $a^{m+n} = a^m \cdot a^n$。应用这一定律，我们可以重写原来的问题：

突然间，问题变了。我们不再需要进行二十次乘法，而只需找出三个特定的三的幂——$3^1$、$3^4$ 和 $3^{16}$——并将它们相乘即可。

但是，我们如何不通过将 $3$ 自乘十五次来得到像 $3^{16}$ 这样的项呢？答案是第二个关键洞见：我们可以通过重复对底数进行平方来构建一个幂的“阶梯”。

从 $3^1$ 开始，我们将其平方得到 $(3^1)^2 = 3^2$。 我们将结果平方得到 $(3^2)^2 = 3^4$。 再次平方：$(3^4)^2 = 3^8$。 再来一次：$(3^8)^2 = 3^{16}$。

仅用四次平方运算，我们就爬到了 16 次幂的阶梯！我们可以以惊人的速度生成所有 2 的次幂——$3^1, 3^2, 3^4, 3^8, 3^{16}, \ldots$。为了防止数字变得天文般巨大，我们在每一步都执行“模”运算。例如，要计算 $3^2 \pmod{25}$，我们做 $3 \times 3 = 9$。要得到 $3^4 \pmod{25}$，我们对该结果进行平方：$9 \times 9 = 81$，即 $6 \pmod{25}$。我们处理的数字永远不必大于模数本身。

通过结合这两个思想——将指数分解为二进制和通过重复平方构建幂——我们有了一种完整且效率惊人的方法。这就是​​平方-乘算法​​，也称为​​二进制取幂​​。有两种优美的方式来形象化它的工作原理。

​​1. 蓝图法（从左到右）​​

此方法将指数的二进制表示作为直接的蓝图。对于 $7^{69} \pmod{101}$，我们首先找到 $69$ 的二进制蓝图。它是 $64+4+1$，即 $(1000101)_2$。然后，我们构建底数 $7$ 的幂的阶梯：$7^1, 7^2, 7^4, \ldots, 7^{64}$，全部对 $101$ 取模。蓝图 1000101 精确地告诉我们在最终的乘积中要使用阶梯的哪些梯级。我们将对应“1”的幂相乘：

我们只需忽略蓝图中对应“0”的幂。这是思考问题结构的一种直观方式。

​​2. 迭代法（从右到左）​​

第二种视角更接近计算机实现该算法的方式。这是一个逐位处理指数的步骤化过程。让我们回到 $3^{21} \pmod{25}$，指数 $21$ 为 $(10101)_2$。我们从右到左处理这些比特位。该过程涉及两个运行变量：一个用于累积最终答案的 result（初始为 $1$）和一个沿平方阶梯攀升的 base_power（初始为 $3^1$）。

对于指数的每一位：

• 如果该位是 1，我们将 result 乘以当前的 base_power。我们可以称之为一个​​乘法​​（Multiplication）步骤（M）。
• 之后，我们总是将 base_power 平方，为下一位做准备。我们称之为一个​​平方​​（Squaring）步骤（S）。

让我们对 $(10101)_2$ 进行追踪：

• ​​第 0 位 (1):​​ 是 1。执行 M（result 变为 $1 \times 3 = 3$）。然后执行 S（base_power 变为 $3^2=9$）。
• ​​第 1 位 (0):​​ 是 0。跳过 M。执行 S（base_power 变为 $9^2=81 \equiv 6 \pmod{25}$）。
• ​​第 2 位 (1):​​ 是 1。执行 M（result 变为 $3 \times 6 = 18$）。执行 S（base_power 变为 $6^2=36 \equiv 11 \pmod{25}$）。
• ​​第 3 位 (0):​​ 是 0。跳过 M。执行 S（base_power 变为 $11^2=121 \equiv 21 \pmod{25}$）。
• ​​第 4 位 (1):​​ 是 1。执行 M（result 变为 $18 \times 21 = 378 \equiv 3 \pmod{25}$）。执行 S（我们已经处理完所有位，所以这最后一次平方是不必要的）。

最终结果是 $3$。平方的次数与指数的比特数有关，而乘法的次数恰好是指数二进制形式中“1”的个数（汉明权重）。

这些方法感觉像是聪明的技巧。但为什么它们能保证奏效呢？深层原因在于一个优美的数学概念，称为​​循环不变量​​。想象算法是一台转换一组三个数 $(r, b, e)$ 的机器——即当前结果、当前底数幂和剩余指数。在最开始，我们将这三元组设为 $(1, \text{base}, \text{exponent})$。

神奇之处在于：在计算的每一步，量 $r \cdot b^e$ 都与我们寻找的最终答案等价。这个性质就是不变量——贯穿整个过程并保持为真的“逻辑金线”。

让我们看看机器如何保持这个不变量。假设当前指数 $e$ 是奇数。我们可以写出 $b^e = b \cdot b^{e-1}$。我们的不变量是 $r \cdot b \cdot b^{e-1}$。为了进入下一步，算法转换三元组：

• 结果 $r$ 更新为 $r' = r \cdot b$。
• 指数 $e$ 变为 $e' = e-1$。 新的不变量是 $r' \cdot b^{e'} = (r \cdot b) \cdot b^{e-1}$，这与我们开始时完全相同。

现在，假设指数（我们称之为 $e'$）是偶数。我们可以写出 $b^{e'} = (b^2)^{e'/2}$。算法执行另一次转换：

• 底数 $b$ 更新为 $b' = b^2$。
• 指数 $e'$ 变为 $e'' = e'/2$。 新的不变量是 $r \cdot (b')^{e''} = r \cdot (b^2)^{e'/2}$，这再次与我们开始时完全相同。

算法只是重复这两个转换，它们被设计用来完美地保持不变量，同时系统地减小指数。最终，指数变为 $0$。在最后这一刻，不变量告诉我们：

累积的结果 $r_{final}$ 必须是正确答案。这个聪明的技巧被揭示为一个优美而严谨的数学逻辑。

平方-乘算法不仅仅是节省了一点时间；它将计算上不可能的事情变成了微不足道的小事。重复乘法的朴素方法需要与指数 $e$ 成正比的步数。而平方-乘算法需要的步数与指数的比特数成正比，大约是 $\log_2(e)$。

这在实践中意味着什么？让我们以 RSA 密码学中一个典型的指数为例，它可能有 2048 位。这个指数 $e$ 的值是巨大的，大约为 $2^{2047}$。

• ​​朴素方法​​：需要约 $2^{2047}$ 次乘法。这个数字如此之大，以至于可观测宇宙中的原子数量都不足以写下它。这就是“宇宙热寂”式的计算。
• ​​平方-乘方法​​：需要大约 $2 \times 2048 = 4096$ 次乘法。一台现代计算机在不到一秒的时间内就能完成。

这种差异不仅仅是程度上的，而是不可能与现实之间的区别。这种效率不仅仅是一种便利；它是使现代公钥密码学（如 RSA）成为可能的基础。

故事在这里转向了真正深刻的地方。平方-乘算法实际上并不关心数字。它真正的力量在于其通用性。它唯一依赖的性质是​​结合性​​：即 $(x \cdot y) \cdot z = x \cdot (y \cdot z)$。任何具有结合运算的系统——一种称为​​独异点​​的数学结构——都是这个算法的游乐场。

考虑 $2 \times 2$ 矩阵的集合。矩阵乘法是结合的，但众所周知它是​​不可交换的​​（$A \cdot B$ 通常不等于 $B \cdot A$）。算法还能工作吗？当然能！因为它执行的所有乘法都是在同一个基础矩阵的幂之间进行的（例如，$A^p \cdot A^q$），而单个元素的幂总是相互交换的（$A^p \cdot A^q = A^{p+q} = A^{q+p} = A^q \cdot A^p$）。算法的正确性从未依赖于普遍的交换性，只依赖于结合性。

这意味着我们可以使用平方-乘来计算任何东西的幂：矩阵、置换、变换、抽象代数群的元素——应有尽有。模幂运算只是一个更深层、更普遍的计算原理的一种表现形式，一种伪装。

这个视角也澄清了逆元的作用。要计算 $a^{-117}$，我们需要能够找到 $a^{-1}$。这要求我们的元素 $a$ 是一个​​单位元​​——一个具有乘法逆元的元素。在模运算的世界里，一个整数 $a$ 是模 $n$ 的单位元，当且仅当 $\gcd(a,n)=1$。如果这个条件满足，我们可以找到逆元 $a^{-1}$，然后应用标准的平方-乘算法来计算 $(a^{-1})^{117}$。至关重要的是要理解，当 $e$ 为正数时，幂运算 $a^e \pmod n$ 对任何整数 $a$ 都是良定义的，但对于负指数，我们必须将自己限制在单位元的世界里。

回到计算的现实世界，故事还有一个引人入胜的转折。算法很快，但我们能让它更快吗？可以。我们可以不逐位读取指数，而是以每次 $w$ 位的块来读取。这被称为​​窗口求幂法​​。它需要少量预计算（存储像 $a^3, a^5, a^7, \ldots$ 这样的值），但可以减少主循环中的乘法次数，用少量内存换取速度提升。

但在密码学的世界里，纯粹的速度可能是一把双刃剑。标准的平方-乘算法只有在秘密指数中看到“1”时才执行乘法步骤。这意味着运行所需的总时间取决于“1”的数量！一个拥有非常精确秒表的攻击者可以测量你的计算机执行加密操作所需的时间。通过观察这些微小的时间差异，他们可以推断出你密钥中“1”的数量——这是一种毁灭性的信息泄露，称为​​时间攻击​​。

我们如何防御这样聪明的对手？通过牺牲一点性能来换取安全。解决方案是设计一个​​常数时间​​版本的算法。在这个变体中，计算机对指数的每一位都执行一次乘法。如果该位是“1”，它就是一次真正的乘法。如果该位是“0”，它就是一次“伪”乘法，对结果没有影响，但花费的时间完全相同。总执行时间现在与秘密指数的值无关。对于每一个密钥，时钟的走时都是一样的。

这就产生了一种权衡。常数时间的实现本质上比可变时间的版本慢，带来了性能开销。对于一个典型的 2048 位指数，这种安全措施会使计算慢大约 $33\%$。但这就是在一个连时钟的滴答声都可能泄露你最深层秘密的世界里，为安全付出的代价。

从一个计算大数幂的简单愿望出发，我们穿行于二进制数之间，发现了一个优雅而强大的算法，揭示了其在抽象代数中的深层数学基础，并最终直面了现实世界中性能与安全之间的微妙博弈。平方-乘算法不仅仅是一个技巧；它是数学思维之美、统一性及其实践力量的完美典范。

在我们深入了解了平方-乘算法的内部工作原理之后，人们可能会倾向于将其归类为一个聪明但小众的计算技巧。这就好比发现了杠杆原理后，得出结论说它只对举起某块特定的石头有用！该算法真正的力量和美妙之处不仅在于其机制本身，还在于其惊人的普适性。它是一种通用的计算杠杆，让我们能以对数时间解决那些看似无法逾越的问题。它的应用从我们数字安全的基石延伸到纯数学和计算机科学的抽象前沿。让我们来探索这片领域，看看这个简单的想法能带我们走多远。

平方-乘算法最能改变世界的应用可能是在公钥密码学中，这项技术保护着从你的银行交易到私人消息的一切。像 Diffie-Hellman 密钥交换和 RSA 加密这样的协议建立在一个迷人的不对称性之上：某些数学运算在一个方向上很容易执行，但在反向上却极其困难。模幂运算，即计算 $g^a \pmod{p}$，就是一个典型的例子。

想象两个人，Alice 和 Bob，需要在一个公共信道上商定一个秘密密钥。他们可以使用 Diffie-Hellman 协议，这涉及他们双方都计算一个公共底数的幂。Alice 可能需要计算像 $5^{13} \pmod{23}$ 这样的值。朴素的方法需要 12 次乘法。但如果指数有数百位长呢？步数将是天文数字。然而，使用平方-乘算法，Alice 可以在寥寥几步内计算出这个值，操作次数只与指数的位数成正比。正是这种效率使得这些密码系统变得实用。与此同时，安全性来自于一个事实，即窃听者即使看到了结果，也很难找出原始的指数——即所谓的离散对数问题。我们的算法是这条单行道的“容易”方向。

当然，这些密码系统依赖于非常大的素数的可用性。我们如何找到它们？你不能简单地测试每一个可能的因子；对于一个有数百位数字的数来说，这将比宇宙的年龄还要长。取而代之的是，我们使用概率性素性测试，例如费马测试、Solovay-Strassen 测试，以及现代的主力——Miller-Rabin 测试。在这些测试的核心，都存在一个快速的模幂运算。例如，为了测试一个数 $n$，我们可能会检查 $a^{n-1} \equiv 1 \pmod{n}$ 是否对某个底数 $a$ 成立。如果没有一个高效的算法来完成这个幂运算，找到大素数将是不可能的，现代密码学也根本不会存在。

这种联系甚至可以更深刻。Miller-Rabin 测试不仅仅是使用该算法；其结构本身就是算法机制的优美反映。该测试需要将 $n-1$ 分解为 $2^s d$ 的形式，然后从 $a^d$ 开始检查一系列的平方。这个顺序平方的过程正是平方-乘算法所做的，使得该测试能够有效地探测出揭示一个数是合数的数学性质 [@problem_d:3092121]。我们甚至可以进一步优化这些密码学计算。例如，在 RSA 中，中国剩余定理可以与我们的算法结合，将一个大的幂运算分解为两个较小的幂运算，有效地在两个较小的问题上并行使用我们的计算杠杆，从而实现显著的加速。

远在密码学应用之前，对数的研究——数论——被认为是数学最纯粹的形式之一。然而，我们这个实用的算法在这里也找到了用武之地，为探索数的​​基本性质提供了一个强大的工具。

考虑这个问题：形式为 $x^2 \equiv a \pmod{p}$ 的方程是否有解？这是确定 $a$ 是否是模素数 $p$ 的“二次剩余”的问题。一个被称为欧拉准则的优美结果表明，我们可以通过简单地计算 $a^{(p-1)/2} \pmod p$ 来回答这个问题。如果结果是 $1$，则存在解；如果是 $-1$，则不存在解。对于一个大的素数 $p$，计算这个幂会很艰巨，但有了平方-乘算法，它对计算机来说就成了一项微不足道的任务，将一个深刻的理论问题变成了一个直接的计算。

然而，一个优秀的科学家——就像一个优秀的工程师一样——知道拥有一个强大的工具并不意味着它适用于所有工作。这给我们带来了算法思维中的一个重要教训。假设我们需要计算一个模逆元，$a^{-1} \pmod n$。对于一个素数模 $n$，费马小定理告诉我们 $a^{n-1} \equiv 1 \pmod n$，这意味着 $a \cdot a^{n-2} \equiv 1 \pmod n$。所以，逆元就是 $a^{n-2} \pmod n$，我们可以用我们的算法高效地计算这个值。但这是最快的方法吗？事实证明，一个更古老的方法，即扩展欧几里得算法，也能找到逆元。对位运算次数的仔细分析表明，欧几里得算法实际上渐近更快！。这是一个绝妙的洞见：即使有了像平方-乘这样杰出的工具，我们也必须保持批判性思维，并始终比较不同的方法以找到最高效的解决方案。

这里，我们的理解将实现一个巨大的飞跃。平方-乘算法实际上根本不关心数字。它的力量来自一个单一的、抽象的性质：结合性。该算法适用于任何对象集合和任何运算“$\ast$”，只要 $(x \ast y) \ast z = x \ast (y \ast z)$。这一认识开启了一个充满应用可能性的宇宙。

思考著名的斐波那契数列，其中每一项是前两项之和。要找到第十亿项 $F_{10^9}$，我们需要计算它之前的所有项吗？不！我们可以将递推关系编码成一个矩阵：

要找到第 $n$ 个斐波那契数，我们只需要计算这个矩阵的 $n$ 次幂。由于矩阵乘法是结合的，我们可以使用平方-乘算法在对数步数内计算出这个幂，使我们能够瞬间跳跃到答案。

这个思想甚至可以延伸得更远。考虑一个图，一个由节点和连接组成的网络。我们如何确定从节点 $s$ 到节点 $t$ 是否存在一条长度恰好为 $k$ 的路径？这个来自计算复杂性理论的问题似乎与幂运算相去甚远。然而，如果我们用其邻接矩阵 $A$ 来表示图，并使用一种特殊的算术（布尔半环，其中加法是“或”运算，乘法是“与”运算）进行矩阵乘法，那么 $(A^k)_{s,t}$ 的条目为真当且仅当这样的路径存在。我们再次可以通过使用我们可靠的算法计算矩阵幂 $A^k$ 来高效地找到这个答案。算法的领域已经扩展到包括图和路径查找。我们甚至可以再次改变算术，使用一个加法是按位异或、乘法是按位与的半环，算法同样适用，在理论计算机科学的其他角落找到了用途。

这段抽象之旅将我们带回了密码学，但处于一个更高的层面。现代椭圆曲线密码学使用曲线上的点作为其基本对象。一个点 $P$ 与一个整数 $k$ 的“乘法”（写作 $[k]P$）被定义为将该点与自身相加 $k$ 次。这种点加法是结合的。因此，要计算一个非常大的 $k$ 的 $[k]P$，我们不执行数十亿次加法。相反，我们使用“倍点-加点算法”——这不过是在曲线上点的群的加法语言中表达的平方-乘算法。

从保护数字消息到求解斐波那契数，从测试素性到遍历图，我们看到同一个优美的思想在发挥作用。平方-乘算法是数学和计算机科学中抽象力量的明证。它展示了一个单一、优雅的原则，一旦以其真实的、普遍的形式被理解，就可以成为解开大量看似无关问题的钥匙。它确实是一个通用的杠杆。