pts*_*pts 11 javascript primes discrete-mathematics modulo exponentiation
我的问题是(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的建议做一些额外的准备工作(即预先计算几百个权力),可以做到2048-位模幂运算仅使用最多354次模乘.(传统的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),然后才恢复到基础-32768 O( n ^ 2)在BigInt中实现的乘法.对于2048位整数,这会使乘法乘以2.25倍.不幸的是,模运算不会变得更快.
更新:使用http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf和Karatsuba乘法和预计算功能中定义的修改后的Barrett约简(在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)解释可高达6.5倍,比在Firefox 3.0的JavaScript解释器速度更快,如果int是用来代替Number,并Vector.<int>用来代替Array.对于2048位大整数乘法,至少它快2.41倍.因此,在AS3中进行模幂运算可能是值得的,如果可用的话,在Flash Player 10中执行它.请注意,这仍然比谷歌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#)吗？
可以从 JS 调用的其他一些客户端技术（例如 Java 小程序或 Flash 电影）是否可以接受？Leemon 的实现（基于Montgomery Reduction）已经相当快了。您可以调整 BigInt，或者可以尝试不同的算法，但您可能不会获得数量级的改进。
| 归档时间： |
|
| 查看次数： |
6129 次 |
| 最近记录： |