二进制幂是如何工作的？

二进制幂（也称为平方求幂法）将指数转换为二进制，然后从左到右处理每个位。对于每个位，它会对当前结果进行平方（取模）。如果该位为 1，它还会乘以底数（取模）。这将乘法次数从 b-1 次减少到最多 2*log2(b) 次。

模幂运算计算器

使用二进制指数（快速幂）算法高效计算模幂 a^b mod n。输入底数、指数和模数即可立即获得结果，并包含平方乘算法的逐步分解、二进制分解可视化以及密码学背景知识。

模幂运算计算器

模幂运算计算器用于计算 \(a^b \bmod n\) —— 将底数 \(a\) 提升到指数 \(b\) 幂，并取除以模数 \(n\) 后的余数。它使用二进制幂算法（也称为快速幂或平方求幂法），该算法将操作从 \(O(b)\) 次乘法减少到仅 \(O(\log b)\) 次。这是在 RSA、Diffie-Hellman 和 ElGamal 等现实世界密码学实现中使用的相同算法。

模幂运算的应用

🔐

RSA 加密

使用大质数乘积的模幂运算来加密和解密消息

🤝

Diffie-Hellman

用于安全共享密钥的密钥交换协议，计算 g^a mod p

✍

数字签名

DSA、ECDSA 和 EdDSA 都依赖于模幂运算

🧪

素性测试

费马和 Miller-Rabin 测试使用 a^(n-1) mod n 来检查素性

🏆

算法竞赛

带有快速幂的模运算是竞赛编程中必不可少的基础

🔗

区块链

工作量证明和加密哈希函数依赖于模运算

二进制幂算法的工作原理

核心思路是我们可以利用二进制表示，将任何指数分解为 2 的幂之和。例如，\(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\)，因此 \(a^{13} = a^{8} \times a^{4} \times a^{1}\)。

该算法从左到右处理指数的二进制数字：

第 1 步：将指数 \(b\) 转换为二进制。

第 2 步：初始化结果 = 1（如果第一位是 1，则结果 = 底数）。

第 3 步：对于后续的每一位：对结果进行平方（取模 n）。如果该位为 1，则还需乘以底数（取模 n）。

第 4 步：处理完所有位后，结果即为 \(a^b \bmod n\)。

伪代码

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // 位为 1
            result = (result × base) mod mod
        exp = exp >> 1        // 右移（除以 2）
        base = (base × base) mod mod
    return result

关键公式

属性	公式	描述
模幂运算	\(a^b \bmod n\)	a^b 除以 n 的余数
费马小定理	\(a^{p-1} \equiv 1 \pmod{p}\)	适用于质数 p 且 gcd(a,p)=1 的情况
欧拉定理	\(a^{\phi(n)} \equiv 1 \pmod{n}\)	适用于 gcd(a,n)=1 的情况，φ 是欧拉函数
二进制法复杂度	\(O(\log b)\) 次乘法	最多进行 2·log₂(b) 次模乘
RSA 加密	\(c = m^e \bmod n\)	使用公钥 (e, n) 加密消息 m
RSA 解密	\(m = c^d \bmod n\)	使用私钥 d 解密密文 c

如何使用模幂运算计算器

输入底数 (a): 这是你要求幂的数字。它可以是正数或负数。例如，计算 7^256 mod 13 时请输入 7。
输入指数 (b): 这必须是一个非负整数。它代表幂次。对于密码学应用，这个值可能非常大（本计算器支持高达 10^18 的数值）。
输入模数 (n): 这必须是一个正整数。它是你用来除以并获取余数的数字。在 RSA 中，这通常是两个大质数的乘积。
点击计算: 计算器使用二进制幂运算计算 a^b mod n，并立即显示结果。
观看动画: 点击“播放”观看二进制幂算法的逐步执行过程。指数的每一位按顺序处理，显示算法是在进行“平方”还是“平方并乘法”。
查看追踪: 分步表格显示了每一次中间计算，而效率对比则显示了二进制幂运算比朴素的重复乘法快多少。

为什么二进制幂运算非常快

考虑计算 \(2^{1000} \bmod 13\)。朴素的方法需要 999 次乘法。二进制幂运算将 1000 转换为二进制 (1111101000)，它有 10 位。它只需要最多 9 次平方加上为每个“1”位进行的几次乘法 —— 总共大约 15 次操作。这减少了约 98.5% 的操作次数。对于具有数百位数字的密码学规模指数，其差异是天文数字般的：二进制方法需要数千次操作，而朴素方法所需的操作次数将超过宇宙中的原子总数。

常见问题解答

什么是模幂运算？

模幂运算计算的是 (a^b) mod n —— 它先对底数求指数幂，然后取除以模数后的余数。它是公钥密码学（RSA, Diffie-Hellman, ElGamal）的核心操作，并广泛用于数论、算法竞赛和计算机科学。二进制幂方法通过 O(log b) 次乘法高效地计算该值。

二进制幂（平方求幂）是如何工作的？

二进制幂将指数转换为其二进制表示，然后从左到右（或从右到左）处理每个位。对于每个位，它会对当前结果进行模 n 平方。如果该位为 1，它还会将结果乘以模 n 后的底数。这将乘法次数从 b−1（朴素方法）减少到最多 2×log₂(b)，使得计算巨大的指数成为可能。

为什么模幂运算在密码学中很重要？

RSA 加密计算 c = m^e mod n 进行加密，计算 m = c^d mod n 进行解密，其中 n 是两个大质数的乘积，指数可能有数百位长。如果没有快速模幂运算，这些操作在计算上是不可能的。其安全性基于以下事实：反向操作（计算离散对数）被认为在计算上是不可行的。

底数可以是负数吗？

是的，完全支持负底数。计算器首先底数对 n 取模（使用 Python 的模运算，对于正数 n 总是返回非负结果）。例如，(−3)^2 mod 7 = 9 mod 7 = 2。由于取模运算总是产生 [0, n−1] 范围内的值，因此不会出现负数结果。

当模数为 1 时会发生什么？

任何整数对 1 取模都等于 0。这是因为任何整数除以 1 得到的都是整数本身，余数为 0。因此对于所有 a 和 b 的值，a^b mod 1 = 0。计算器会将其作为特殊情况处理。

引用此内容、页面或工具为：

"模幂运算计算器" 于 https://MiniWebtool.com/zh-cn/模幂运算计算器/，来自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 团队制作。更新日期：2026-04-16

您还可以尝试我们的 AI数学解题器 GPT，通过自然语言问答解决您的数学问题。

其他相关工具:

模幂运算计算器