JavaScript 中的 BigInt

之前写 JavaScript 代码,有听说到Number.MAX_VALUENumber.MAX_SAFE_INTEGER,但是一直没有做深入的理解,对Number.MAX_SAFE_INTEGER并不太了解。

遇到的问题

要从一个密码学实验代码说起,最近在用 JavaScript 实现 RSA 算法,遇到了一个问题。RSA 算法是基于大质数乘积的因式分解困难的难题实现的。

其中,生成密钥对的大致步骤如下:

  1. 随机生成两个大质数 p,q;
  2. 计算 n=p*q;
  3. 计算 m=(p-1)*(q-1);
  4. 计算数值 e,e 为一个与 m 互质的数
  5. 计算数值 d,d 为满足(d*e) ≡ 1 mod m 的数

在生成d时遇到了一个问题,generateD()生成的d不符合我的预期,但是计算步骤是没问题的。

const generateD = (e, m) => {
  let k = 1;
  while (true) {
    if ((k * m + 1) % e === 0) {
      return (k * m + 1) / e;
    }
    k++;
  }
};

排查发现当 k=5,m=9999999999999999,e=10时,if 的条件语句为真,但是从数学的角度来说,此时(k*m+1)%e显然是 6。

console.log((5 * 9999999999999999 + 1) % 10);
// 结果为0

怀疑是数值太大的原因改用 BigInt,才解决了问题。

console.log((5n * 9999999999999999n + 1n) % 10n);
// 结果为6n

重新修改generateD函数

const generateD = (e, m) => {
  let k = 1n;
  e = BigInt(e);
  m = BigInt(m);
  while (true) {
    if ((k * m + 1n) % e === 0n) {
      return parseInt((k * m + 1n) / e);
    }
    k++;
  }
};

原因分析

原因在于 JavaScript 中的Number无论是整数还是小数都是使用 IEEE754 的双精度浮点数表示的。

双精度浮点数

双精度浮点数的表示类似与科学计数法(-1)^S*(1.M)*2^(E-1023)

由符号位(d63),指数部分(d62-d52),尾数部分(d51-d0)组成。符号位决定了这个浮点数的正负,指数部分决定了这个数的表示范围,尾数部分决定了这个数的表示精度。如果尾数部分太长,那么多余的部分只能舍去,此时浮点数的精度就降低了。

Float Point Converter

因此有了Number.MAX_SAFE_INTEGER。它的值为90071992547409911, 当数值超过Number.MAX_SAFE_INTEGER时,就不能保证数值的精度了。可以调用Number.isSafeInteger进行判断。

Number.MAXSAFEVALUE[2] : The value of Number.MAX_SAFE_INTEGER is the largest integer n such that n and n + 1 are both exactly representable as a Number value.

BigInt

我们可以用 BigInt 来表示任意大的整数,但也有需要注意的地方

  1. 不可以和 Number 实例混用
  2. 不能用于 Math 对象中的方法
  3. 使用 BigInt 运算时,带小数的结果会被取整
  4. 在 JSON 中使用时,需要自己实现BigInt.prototype.toJSON
  5. 因为对 BigInt 的操作并不是常数时间,因此 BigInt 不适合用于密码学[3]

参考引用