Exponentiation by Squaring

释义 Definition

平方求幂（快速幂）：一种高效计算 \(a^n\) 的算法，通过把指数不断“二分”并利用平方运算，将时间复杂度从朴素方法的 \(O(n)\) 降到 \(O(\log n)\)。常用于大整数运算、模幂运算与密码学中。（也常被称为 binary exponentiation。）

发音 Pronunciation (IPA)

/ˌɛkspəˌnɛnʃiˈeɪʃən baɪ ˈskwɛərɪŋ/

例句 Examples

Exponentiation by squaring computes powers in logarithmic time.
平方求幂可以在对数时间内计算幂。

To compute \(a^{10^9} \bmod m\) efficiently, the program uses exponentiation by squaring with modular reduction at each step.
为了高效计算 \(a^{10^9} \bmod m\)，程序使用平方求幂，并在每一步进行取模化简。

词源 Etymology

该术语由两部分构成：exponentiation（“求幂运算”）+ by squaring（“通过平方”）。它描述的核心思想是：当指数为偶数时，\(a^n=(a^{n/2})^2\)；当指数为奇数时，\(a^n=a\cdot a^{n-1}\)，从而把问题递归/迭代地缩小为更小的指数。这一方法在计算数学与计算机算法传统中由来已久，因其主要操作反复出现“平方”而得名。

相关词 Related Words

• Binary Exponentiation
• Fast Exponentiation
• Exponent
• Power
• Square
• Recursion
• Modular Exponentiation
• Logarithm
• Algorithm

文学与名著用例 Literary / Notable Works

• The Art of Computer Programming, Volume 2: Seminumerical Algorithms — Donald E. Knuth（讨论高效幂运算与相关技巧）
• Introduction to Algorithms — Cormen, Leiserson, Rivest, Stein（常以“快速幂/二进制幂”思想出现在算法章节或练习中）
• Concrete Mathematics — Graham, Knuth, Patashnik（在离散数学与算法分析语境中涉及高效幂与递推思想）
• Handbook of Applied Cryptography — Menezes, van Oorschot, Vanstone（在模幂运算与密码学实现背景下常用该方法）