11

我的问题是(g^x) mod p在 JavaScript 中快速计算，^取幂mod是模运算。所有输入都是非负整数，x大约有 256 位，并且p是 2048 位的质数，g最多可以有 2048 位。

我发现的大多数可以在 JavaScript 中执行此操作的软件似乎都使用 JavaScript BigInt 库（http://www.leemon.com/crypto/BigInt.html）。在我的慢速浏览器（带有 SpiderMonkey 的 Firefox 3.0）上，用这个库进行一次这样大小的幂运算大约需要 9 秒。我正在寻找至少快 10 倍的解决方案。对于 2048 位数字来说，使用平方和乘法（通过平方求幂，http ://en.wikipedia.org/wiki/Exponentiation_by_squaring ）的明显想法太慢了：它需要多达 4096 次乘法。

升级浏览器不是一种选择。使用另一种编程语言不是一种选择。将号码发送到 Web 服务不是一种选择。

是否有更快的替代方案实施？

更新：按照下面 outis 的回答中提到的文章http://www.ccrwest.org/gordon/fast.pdf的建议，通过做一些额外的准备（即预先计算几百次幂） ，可以对 2048-位模幂运算最多仅使用 354 次模乘。（传统的平方和乘法方法要慢得多：它使用最多 4096 次模乘。）这样做在 Firefox 3.0 中将模幂运算速度提高了 6 倍，在 Google Chrome 中提高了 4 倍。我们没有得到 4096/354 的完全加速的原因是 BigInt 的模幂算法已经比平方和乘法更快，因为它使用了蒙哥马利归约 ( http://en.wikipedia.org/wiki/Montgomery_reduction ) .

更新：从 BigInt 的代码开始，似乎值得做两级手动优化（和内联）Karatsuba 乘法（http://en.wikipedia.org/wiki/Karatsuba_algorithm），然后才恢复到 base-32768 O( n^2) 在 BigInt 中实现的乘法。这将 2048 位整数的乘法速度提高了 2.25 倍。不幸的是，模运算并没有变得更快。

更新：使用http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf和 Karatsuba 乘法和预计算幂（定义在http://www.ccrwest.org/gordon/ fast.pdf )，我可以在 Firefox 3.0 中将单次乘法所需的时间从 73 秒缩短到 12.3 秒。这似乎是我能做的最好的，但它仍然太慢。

更新：Flash Player 中的 ActionScript 2 (AS2) 解释器不值得使用，因为它似乎比 Firefox 3.0 中的 JavaScript 解释器慢：对于 Flash Player 9，它似乎慢 4.2 倍，对于 Flash Player 10，它似乎慢了 2.35 倍。有人知道 ActionScript2 和 ActionScript3 (AS3) 在数字处理方面的速度差异吗？

更新：Flash Player 9 中的 ActionScript 3 (AS3) 解释器不值得使用，因为它的速度与 JavaScript int Firefox 3.0 几乎相同。

更新：如果使用 Flash Player 10 中的 ActionScript 3 (AS3) 解释器int代替Number，并且Vector.<int>使用代替Array. 2048 位大整数乘法至少要快 2.41 倍。因此，可能值得在 AS3 中进行模幂运算，如果可用，在 Flash Player 10 中执行它。请注意，这仍然比 Google Chrome 的 JavaScript 解释器 V8 慢。有关各种编程语言和 JavaScript 实现的速度比较，请参阅http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html 。

更新：有一个非常快速的 Java 解决方案，如果安装了 Java 插件，可以从浏览器的 JavaScript 调用。以下解决方案比使用 BigInt 的纯 JavaScript 实现快约 310 倍。

<body>hi0
<script type="text/javascript">
document.body.innerHTML += '<br>hi1';
if ('object'==typeof java) {
  var x = new java.math.BigInteger("123456789123456789", 10);
  var p = new java.math.BigInteger("234567891234567891", 10);
  var g = new java.math.BigInteger("3", 10);
  var v = x.modPow(x, p);
  document.body.innerHTML += '<br>' + v.toString();
  document.body.innerHTML += '<br>' + v.toString(16);
} else {
  document.body.innerHTML += '<br>java plugin not installed';
}
</script></body>

任何人都可以将此代码翻译成 Silverlight (C#) 吗？

4

4 回答 4

4

我使用“%”表示模块化（mod），使用“/”表示整数除法。让函数 f(p,g,x,r) 在 r<p 和 g<p 的条件下计算 (r*g^x)%p。f() 可以实现为：

bigint_t f(p,g,x,r) {
  bigint_t i, z = g, y;
  for (i = 1; i < x; ++i) {
    y = z; z *= g;
    if (z > p) break;
  }
  if (i >= x - 1) return r*z%p; // g^x*r%p = g^x*r
  else return f(p,y,x/i,g^(x%i)*r%p); // reduce to (r*g^(x%i)%p)*(g^i)^(x/i)%p
}

此例程涉及更多计算，但每个整数小于 4096 位，通常比 g^x 小得多。我相信这可能比直接计算更有效。另请注意，g^(x%i) 可以以更快的方式计算，因为我们已经计算了 g^(i+1)。

编辑：见这篇文章。Mehrdad 给出了正确（和更好）的解决方案。

于 2009-09-20T09:51:22.370 回答
4

其他一些可从 JS 调用的客户端技术，例如 Java 小程序或 Flash 电影，是否可以接受？BigInt 的方法已经相当快了。您可以调整 BigInt，或者您可以尝试不同的算法，但您可能不会获得数量级的改进。

于 2009-09-21T11:53:17.810 回答
2

为什么不使用像 C 这样更合适的语言在某种 Web 服务中做服务器端呢？时间将是一次往返的时间（少于 9 秒），加上服务器使用本机代码中的某些 BigInt 库计算结果的时间。这可能会快得多。

于 2009-09-20T08:55:22.917 回答
2

试试这个来自http://code.google.com/p/bi2php/在 JavaScript 上的Montgomery 模块化简化。

于 2009-10-18T20:13:14.990 回答