JavaScript 中最快的模幂运算
https://stackoverflow.com/questions/1450608
-
11-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我的问题是计算 (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 倍的解决方案。使用平方乘法的明显想法（通过平方求幂， http://en.wikipedia.org/wiki/Exponentiation_by_squaring) 对于 2048 位数字来说太慢：它最多需要 4096 次乘法。
升级浏览器不是一个选择。使用另一种编程语言不是一种选择。将号码发送到网络服务不是一种选择。
是否有更快的替代方案？
更新：通过做一些额外的准备（即按照文章的建议预先计算几百次幂） http://www.ccrwest.org/gordon/fast.pdf 正如下面 outis 的回答中提到的，最多仅使用 354 次模乘即可完成 2048 位模幂运算。（传统的平方乘法要慢得多：它最多使用 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)，然后才恢复到 BigInt 中实现的以 32768 为底的 O(n^2) 乘法。这使得 2048 位整数的乘法速度提高了 2.25 倍。不幸的是，模运算并没有变得更快。
更新：使用修改后的 Barrett 约简定义 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) 解释器不值得使用，因为它的速度与 Firefox 3.0 中的 JavaScript 几乎相同。
更新：如果满足以下条件，Flash Player 10 中的 ActionScript 3 (AS3) 解释器的速度比 Firefox 3.0 中的 JavaScript 解释器快 6.5 倍： int 被用来代替 Number, ， 和 Vector.<int> 被用来代替 Array. 。2048 位大整数乘法至少快了 2.41 倍。因此，可能值得在 AS3 中进行模幂运算，并在 Flash Player 10 中执行（如果可用）。请注意，这仍然比 Google Chrome 的 JavaScript 解释器 V8 慢。看 http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html 用于比较各种编程语言和 JavaScript 实现的速度。
更新：有一个非常快速的 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#)？
其他提示
我用 “％” 为模块化（MOD）和 “/” 为整数除法。让上是R 此例程包括多一点的计算，但每个整数是小于4096位，其通常比G ^ X小得多。我相信这可能比直接计算更高效。还要注意的是G ^（X％I）可以以较快的方式来计算，因为我们已经计算出G ^（I + 1）。 编辑：请参阅此篇。迈赫达德给出正确的（和更好的）解决方案。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
}
为什么不去做服务器端使用像C更合适的语言某种Web服务的？那么时间将及时为一个往返（小于9秒为单位），再加上时间服务器计算使用本地代码一些BigInt有库的结果。这很可能是要快得多。
尝试从 http://code.google.com/p/bi2php/此Montgomery模还原的上的JavaScript。
我很乐意看到源代码，修改后的BigInt有图书馆？ - 是可在任何地方
