当我在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;
}

维基百科的文章有一个详细的描述，但它基本上做的是将xe分成x的乘积，使其与e的二进制表示中的每个设置位对应的数字的幂相对应。例如，x13 == x8×x4×x1（因为1310 == 11012）。这可以通过在每个步骤处对x进行平方并且在每次计算之后应用模数来有效地计算，使得数字不会变得太大。

正如其他人所说，你需要一个big number library来处理真实世界的RSA密钥。

Answer 2

我使用bignum来规避js中大数的极限。

https://www.npmjs.com/package/bignum

您的代码看起来像这样：

var result = bignum(m).pow(d).mod(n)
// or more consicely
var result = bignum(m).powm(d, n)