我的问题是计算 (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倍的解决方案。使用square-and-multiply的明显想法(通过平方取幂, http://en.wikipedia.org/wiki/Exponentiation_by_squaring)对于2048位数字来说太慢了:它需要多达4096次乘法。
升级浏览器不是一种选择。使用其他编程语言不是一种选择。将数字发送到Web服务不是一种选择。
是否有更快的替代方案实施?
更新:按照文章的建议做一些额外的准备工作(即预先计算几百个权力) 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)。
更新:从BigInt的代码开始,似乎值得做两个级别的手动优化(和内联)Karatsuba乘法(http://en.wikipedia.org/wiki/Karatsuba_algorithm),然后才恢复到BigInt中实现的base-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)解释器不值得使用,因为它与JavaScript int Firefox 3.0的速度几乎相同。
更新:Flash Player 10中的ActionScript 3(AS3)解释器的速度比Firefox 3.0中的JavaScript解释器快6.5倍 int
用来代替 Number
,和 Vector.<int>
用来代替 Array
。对于2048位大整数乘法,至少它快2.41倍。因此,在AS3中进行模幂运算可能是值得的,如果可用的话,在Flash Player 10中执行它。请注意,这仍然比谷歌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#)吗?