问题 JavaScript中最快的模幂运算


我的问题是计算 (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#)吗?


7403
2017-09-20 08:48


起源



答案:


可以接受一些可以从JS调用的客户端技术,例如Java applet或Flash电影吗? BigInt有公司 途径 已经相当快了。你可以调整BigInt,或者你可以尝试一下 不同的算法,但你可能不会得到一个数量级的改进。


4
2017-09-21 11:53



我必须确认BigInt已经过很好的优化。我尝试使用Karatsuba算法实现乘法,但它变得比BigInt的简单O(n ^ 2)乘法慢4倍。 - pts
谢谢你提到这篇论文,看起来很有希望。 - pts
使用BigInt.js和你已经链接的文章中的技术,我可以在Firefox 3.0上将2048位整数的模数乘法加速6倍,在谷歌Chrome上加倍4倍。不幸的是,这对我来说仍然太慢,所以我必须找到一个不同的加密协议,这需要更少的计算。 - pts
我想为这个答案提供更多的赞成,因为我发现链接的文章非常有用。但我不能接受它作为答案,因为它仍然不够快。 - pts


答案:


可以接受一些可以从JS调用的客户端技术,例如Java applet或Flash电影吗? BigInt有公司 途径 已经相当快了。你可以调整BigInt,或者你可以尝试一下 不同的算法,但你可能不会得到一个数量级的改进。


4
2017-09-21 11:53



我必须确认BigInt已经过很好的优化。我尝试使用Karatsuba算法实现乘法,但它变得比BigInt的简单O(n ^ 2)乘法慢4倍。 - pts
谢谢你提到这篇论文,看起来很有希望。 - pts
使用BigInt.js和你已经链接的文章中的技术,我可以在Firefox 3.0上将2048位整数的模数乘法加速6倍,在谷歌Chrome上加倍4倍。不幸的是,这对我来说仍然太慢,所以我必须找到一个不同的加密协议,这需要更少的计算。 - pts
我想为这个答案提供更多的赞成,因为我发现链接的文章非常有用。但我不能接受它作为答案,因为它仍然不够快。 - pts


我使用“%”表示模块(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提供了正确(和更好)的解决方案。


3
2017-09-20 09:51



你的实现给了我一个无限递归f(100,3,8,1),而不是返回61.你的算法有一个正确的名称? - pts
对不起,那里有一个小错误。我已经改变了。这个方法只是简单数学的结果,太简单了。 - user172818
该方法基于观察到(k * p + g)^ x%p = g ^ x%p。它重复应用此规则以避免直接计算g ^ x。 - user172818
f在递归调用f时x / i> 2时永远递归,因为y * y> p,所以递归调用中的循环将以i = 1退出。尝试f(100,5,8,1)(只是不是真的,因为你必须杀死你的浏览器)。另请注意 i==floor(log(p)/log(g))。取决于取幂和日志的实现,使用 i=floor(log(p)/log(g)); y=g^i 可能比循环更快。一旦递归问题得到修复,f在最佳情况下在x中将是对数,而在最坏情况下则是x中的sqrt。在所有情况下,通过平方(BigInt使用)的指数在x中是对数的。 - outis


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


2
2017-09-20 08:55



您可能不希望将私钥发送到服务器。 - Steve Gilham
谁说了私钥呢? - 1800 INFORMATION
使用C使用GMP库,速度提高了约1042倍。但是我的问题不是使用不同的编程语言或将数字发送到服务器。 - pts
因此,我认为将它们钉入银光中是因为沉重的嘎吱嘎嘎也是不可能的? - Dan F
我不想将Silverlight作为依赖项。但是如果在浏览器中可用,则使用bigint或Java的bigint是可行的。但在这个问题中,我需要一个在JavaScript中实现快速模幂运算的解决方案。 - pts


试试这个Montgomery模块化减少 http://code.google.com/p/bi2php/ 在JavaScript上。


2
2017-10-18 20:13





我很想看到你修改过的BigInt库的源代码 - 它可以在任何地方使用吗?


1
2017-12-29 17:33



我的代码尚未准备好分享。它绝对不是一个通用的库。 - pts