Binary Exponentiation

释义 Definition

二进制快速幂（又称“平方-乘法 / exponentiation by squaring”）：一种高效计算幂 \(a^n\) 的算法，利用指数 \(n\) 的二进制表示，通过反复“平方”并在需要时“乘上当前底数”，将时间复杂度从朴素的 \(O(n)\) 降到 \(O(\log n)\)。常用于模幂（如 \(a^n \bmod m\)）与密码学、竞赛编程中。

发音 Pronunciation (IPA)

/ˈbaɪnəri ɪkˌspoʊnənʃiˈeɪʃən/

例句 Examples

Binary exponentiation computes \(a^n\) in \(O(\log n)\) time.
二进制快速幂能在 \(O(\log n)\) 时间内计算 \(a^n\)。

In cryptography, binary exponentiation is often used to compute modular powers efficiently without overflow.
在密码学中，二进制快速幂常用于高效计算模幂，从而避免溢出并提升速度。

词源 Etymology

binary 源自拉丁语 bini（“两个一组、成对的”），强调“以 2 为基础/二进制”。exponentiation 来自 exponent（指数），而 exponent 源于拉丁语 exponere（“展示、放出”）；在数学里“指数”用来“展示”幂的次数。该术语合起来强调：用“二进制思路”来做“幂运算”。

相关词 Related Words

• Exponentiation By Squaring
• Power
• Exponent
• Modulo
• Modular Exponentiation
• Logarithmic
• Recursion
• Bitwise
• Fast Power

文学与名著用例 Literary Works

• Introduction to Algorithms（《算法导论》, Cormen et al.）：在数论/模运算相关内容中常提到快速幂（平方-乘法思想）用于高效计算幂与模幂。
• Competitive Programming 3（《程序设计竞赛入门经典（第3版）》, Halim）：作为竞赛常用技巧，讲解快速幂及其在模幂中的应用。
• The Art of Computer Programming, Vol. 2: Seminumerical Algorithms（《计算机程序设计艺术》第二卷, Knuth）：讨论高效算术算法时涉及幂运算的高效计算思想（包含平方-乘法相关方法）。