JavaScript中最快的模幂运算 [英] Fastest modular exponentiation in JavaScript

查看:188
本文介绍了JavaScript中最快的模幂运算的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

My problem is to compute (g^x) mod p quickly in JavaScript, where ^ is exponentiation, mod is the modulo operation. All inputs are nonnegative integers, x has about 256 bits, and p is a prime number of 2048 bits, and g may have up to 2048 bits.

我发现大多数可以在JavaScript中执行此操作的软件似乎使用JavaScript BigInt库( http://www.leemon.com/crypto/BigInt.html )。在我的慢速浏览器(使用SpiderMonkey的Firefox 3.0)上使用此库执行此类大小的单次取幂大约需要9秒。我正在寻找一种至少快10倍的解决方案。使用square-and-multiply的明显想法(通过平方取幂, http://en.wikipedia.org/ wiki / Exponentiation_by_squaring )对于2048位数字来说太慢了:它需要多达4096次乘法。

Most of the software I've found that can do this in JavaScript seems to use the JavaScript BigInt library (http://www.leemon.com/crypto/BigInt.html). Doing a single exponentiation of such size with this library takes about 9 seconds on my slow browser (Firefox 3.0 with SpiderMonkey). I'm looking for a solution which is at least 10 times faster. The obvious idea of using square-and-multiply (exponentiation by squaring, http://en.wikipedia.org/wiki/Exponentiation_by_squaring) is too slow for 2048-bit numbers: it needs up to 4096 multiplications.

升级浏览器不是一种选择。使用其他编程语言不是一种选择。将数字发送到网络服务不是一种选择。

Upgrading the browser is not an option. Using another programming language is not an option. Sending the numbers to a web service is not an option.

是否实施了更快的替代方案?

Is there a faster alternative implemented?

更新:按照文章 http://的建议,做一些额外的准备工作(即预先计算几百个权力) www.ccrwest.org/gordon/fast.pdf 在下面的outis'回答中提到,可以使用最多354次模乘,进行2048位模幂运算。 (传统的square-and-multiply方法要慢得多:它使用最多4096次模乘。)这样做可以在Firefox 3.0中将模幂运算速度提高6倍,在Google Chrome中提高4倍。我们没有得到4096/354的全速加速的原因是BigInt的模块化指数算法已经比正方形和乘法更快,因为它使用蒙哥马利减少( http://en.wikipedia.org/wiki/Montgomery_reduction )。

Update: By doing some extra preparations (i.e. precomputing a few hundred powers) as recommended by the article http://www.ccrwest.org/gordon/fast.pdf mentioned in outis' answer below, it is possible do to a 2048-bit modular exponentiation using only at most 354 modular multiplications. (The traditional square-and-multiply method is much slower: it uses maximum 4096 modular multiplications.) Doing so speeds up the modular exponentiation by a factor of 6 in Firefox 3.0, and by a factor of 4 in Google Chrome. The reason why we are not getting the full speedup of 4096/354 is that BigInt's modular exponentation algorithm is already faster than square-and-multiply, because it uses Montgomery reduction (http://en.wikipedia.org/wiki/Montgomery_reduction).

更新:从BigInt开始代码,似乎值得做两个级别的手动优化(和内联)Karatsuba乘法( http:// en。 wikipedia.org/wiki/Karatsuba_algorithm ),然后才恢复到BigInt中实现的base-32768 O(n ^ 2)乘法。对于2048位整数,这会使乘法乘以2.25倍。不幸的是,模运算不会变得更快。

Update: Starting from BigInt's code, it seems worthwhile doing two levels of hand-optimized (and inlined) Karatsuba multiplication (http://en.wikipedia.org/wiki/Karatsuba_algorithm), and only then revert to the base-32768 O(n^2) multiplication implemented in BigInt. This speeds up multiplications by a factor of 2.25 for 2048-bit integers. Unfortunately, the modulo operation does not become faster.

更新:使用 http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf 和Karatsuba乘法和预计算能力(如 http://www.ccrwest.org/gordon/fast.pdf ),我可以下来Firefox 3.0中单次乘法从73秒到12.3秒所需的时间。这似乎是我能做的最好的,但它仍然太慢。

Update: Using the modified Barrett reduction defined in http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf and Karatsuba multiplication and precomputing powers (as defined in http://www.ccrwest.org/gordon/fast.pdf), I can get down the time needed for a single multiplication from 73 seconds to 12.3 seconds in Firefox 3.0. This seems to be the best I can do, but it is still too slow.

更新:Flash Player中的ActionScript 2(AS2)解释器不值得使用,因为它似乎比Firefox 3.0中的JavaScript解释器慢:对于Flash Player 9,它似乎慢了4.2倍,而对于Flash Player 10,它似乎慢了2.35倍。有没有人知道ActionScript2和ActionScript3(AS3)之间的数字运行速度差异?

Update: The ActionScript 2 (AS2) interpreter in the Flash Player isn't worth using, because it seems to be slower than the JavaScript interpreter in Firefox 3.0: for Flash Player 9, it seems to be 4.2 times slower, and for Flash Player 10, it seems to be 2.35 times slower. Does anybody know the speed difference between ActionScript2 and ActionScript3 (AS3) for number chrunching?

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

Update: The ActionScript 3 (AS3) interpreter in Flash Player 9 isn't worth using because it has just about the same speed as the JavaScript int Firefox 3.0.

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

Update: The ActionScript 3 (AS3) interpreter in Flash Player 10 can be up to 6.5 times faster than the JavaScript interpreter in Firefox 3.0 if int is used instead of Number, and Vector.<int> is used instead of Array. At least it was 2.41 times faster for 2048-bit big integer multiplication. So it might be worth doing the modular exponentiation in AS3, executing it in Flash Player 10 if available. Please note that this is still slower than V8, the JavaScript interpreter of Google Chrome. See http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html for a speed comparison of various programming language and JavaScript implementations.

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

Update: There is a very fast Java solution, which can be called from the browser's JavaScript if the Java plugin is installed. The following solution is about 310 times faster than the pure JavaScript implementation using BigInt.

<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#)吗?

Can anyone translate this code to Silverlight (C#)?

推荐答案

可以接受一些可以从JS调用的客户端技术,比如Java applet或Flash电影吗? BigInt的方法已经相当快了。您可以调整BigInt,或者您可以尝试不同的算法,但您可能会赢得' t得到一个数量级的改进。

Would some other client side technology that's callable from JS, such as a Java applet or Flash movie, be acceptable? BigInt's approach is already fairly fast. You can tweak BigInt, or you can try a different algorithm, but you probably won't get an order of magnitude improvement.

这篇关于JavaScript中最快的模幂运算的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆