javascript - 当我在 JavaScript 中计算 1000^1000 时如何避免无穷大的结果

Question

我正在尝试制作类似 RSA 的加密程序。因此我需要计算 1069^1099。问题是根据 Javascript，该计算的结果是无穷大。有什么办法可以解决这个问题吗？

var n = 23 * 83;
var e = 87;
var d = 1099;
var m = 1069;
var m = m**d % n; //Result NaN because m**d = infinity

Answer 1

如果您只是在开发不使用大质数的玩具 RSA 密码，那么您可以实现 modular exponentation如下:

function modexp(base, exponent, modulus) {
    var result = 1;
    while (exponent) {
        if (exponent & 1) {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exponent >>= 1;
    }
    return result;
}

维基百科的文章有详细的描述，但基本上是把x^e拆成x的乘积e 的二进制表示中每个设置位对应的数字。例如，x¹³ == x⁸ × x⁴ × x¹(因为 13₁₀ == 1101₂)。这可以通过在每一步对 x 进行平方并在每次计算后应用模数来有效计算，这样数字就不会变得太大。

正如其他人所说，您需要一个 big number library处理现实世界的 RSA key 。