模幂运算计算器

模幂运算计算器

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

模幂运算的应用

二进制幂算法的工作原理

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

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

伪代码

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

关键公式

如何使用模幂运算计算器

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

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

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

常见问题解答