代码之家 › 专栏 › 技术社区 › pts

javascript中最快的模块化求幂

exponentiation discrete-mathematics modulo primes javascript

pts · 技术社区 · 15 年前

我的问题是计算 (g^x) mod p 在javascript中快速运行,其中 ^ 是指数化, mod 是模块操作。所有输入都是非负整数, x 大约有256位,并且 p 是2048位的质数,并且 g 最多可以有2048位。

我在javascript中找到的大多数软件似乎都使用了javascript bigint库。( http://www.leemon.com/crypto/BigInt.html )。在我的慢浏览器上,使用这个库进行这样大小的单次求幂大约需要9秒钟(使用spidermonkey的firefox 3.0)。我正在寻找一种速度至少快10倍的解决方案。使用平方和乘(平方求幂, http://en.wikipedia.org/wiki/Exponentiation_by_squaring )对于2048位数字来说太慢了:它最多需要4096次乘法。

升级浏览器不是一个选项。使用另一种编程语言不是一种选择。向Web服务发送号码不是一个选项。

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

更新:按照本文的建议做一些额外的准备(即预先计算几百个幂)。 http://www.ccrwest.org/gordon/fast.pdf 在下面的outis答案中提到,2048位的模幂运算最多只能使用354个模乘。(传统的平方乘法要慢得多:它最多使用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 reducation http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf 以及Karatsuba乘法和预计算能力(定义见网址:http://www.ccrwest.org/gordon/fast.pdf ,我可以在火狐3.0中把一次乘法所需的时间从73秒减少到12.3秒。这似乎是我能做的最好的,但速度还是太慢了。

更新:flash播放器中的actionscript 2(as2)解释器不值得使用,因为它似乎比firefox 3.0中的javascript解释器慢:对于flash播放器9,它看起来慢4.2倍,对于flash播放器10,它看起来慢2.35倍。有人知道数字chrunning的actionscript2和actionscript3(as3)之间的速度差吗?

更新:flash player 9中的actionscript 3(as3)解释器不值得使用,因为它的速度与javascript in t firefox 3.0差不多。

更新:如果 int 使用而不是 Number 和 Vector.<int> 使用而不是 Array . 对于2048位的大整数乘法来说,它至少快了2.41倍。因此,在AS3中进行模块化求幂可能是值得的,如果可以的话,可以在FlashPlayer10中执行。请注意,这仍然比Google Chrome的JavaScript解释器V8慢。见 http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html 用于各种编程语言和JavaScript实现的速度比较。

更新:有一个非常快的Java解决方案,它可以从浏览器的JavaScript中调用,如果安装了Java插件。下面的解决方案比使用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)?

5 回复 | 直到 13 年前

outis 15 年前

可以从JS调用的其他客户端技术,比如Java小程序还是Flash电影,是可以接受的吗?BigInt approach 已经相当快了。你可以调整bigint,或者尝试 different algorithm 但是你可能不会得到一个数量级的改进。

Community CDub 7 年前

模块(mod)使用“%”,整数除法使用“/”。让函数f(p,g,x,r)计算(r*g^x)%p,条件是r<p和g<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)。

编辑:参见 this post . Mehrdad给出了正确(更好)的解决方案。

1800 INFORMATION 15 年前

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

An6rey 15 年前

尝试蒙哥马利模块化缩减 http://code.google.com/p/bi2php/ 关于JavaScript。

viewcopy 15 年前

我很想看到您修改过的bigint库的源代码-它在任何地方都可用吗?