Javascript 中的平方取幂模无法正常工作？

Question

在过去的几个小时里，我一直在尝试实现 Exponentiation by squaring in Javascript. Basically I've been trying to apply the Fermat Little Theorem 来求解模乘逆。看起来应该是直截了当的，但我得到的结果不正确：

const MAX = 10**9 + 7
const inv2 = expBySquare(2, MAX-2)
// inv2 should be 500000004 but is 437533240

function expBySquare(x, n) {
  if (n < 0) throw 'error'
  if (n === 0) return 1
  if (n === 1) return x

  if (n % 2 === 0) return expBySquare((x * x) % MAX, n / 2) % MAX
  return (x * expBySquare((x * x) % MAX, (n - 1) / 2)) % MAX
}

我刚刚尝试用 C https://onlinegdb.com/H1tsx4TY7 实现该算法并且它没有问题。我知道我应该预料到 JS 会出现溢出问题，但我认为它可以处理这些数字，因为所有弱点都使用了模数。

Answer 1

JavaScript 数字始终使用 64 位浮点格式。因此，您只能使用 52 位的尾数，这会给您有效的 53 位。您场景中的中间值超过了这些值，这将引入舍入误差。第一次发生这种情况是 279,632,277 的平方。这应该是 78,194,210,340,204,729（57 位）但四舍五入为 78,194,210,340,204,730.

Answer 2

I knew that I should expected problems with overflows in JS but I think that it can handle the numbers since the modulo is used in all the weak points.

JavaScript 实际上并没有与 "overflow" 不同的 "integer" 类型；相反，它只有一个 "number" 类型，其值是双精度浮点数并且会出现舍入误差。因此，即使 x * x 的值可以表示为 64 位整数，它也可能无法完全表示为 JavaScript 数字。 JavaScript 数字可以精确表示 [−(2⁵³ −1), 2⁵³ −1] 范围内的任何整数 — 请参阅https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER — 但您的计算涉及该范围之外的值。

要亲眼看看您是否在该范围之外冒险，您可以插入：

if (x * x > Number.MAX_SAFE_INTEGER)
    throw 'error: ' + x + ' * ' + x + ' is ' + (x * x);

你会看到错误：294967268 * 294967268 是 8700568919138382<strong>0</strong> 即使 294,967,268 × 294,967,268 实际上是 8,7005,689,191,383,82 4.

要解决此问题，您需要较小的 MAX 值（以确保 MAX * MAX <= Number.MAX_SAFE_INTEGER），或者使用（部分）大整数库对大整数执行整数运算您正在使用的值。

Javascript 中的平方取幂模无法正常工作？

Modulo of exponentiation by square in Javascript not working correctly?

javascript

algorithm

modulo