我的问题是如何在JavaScript中快速计算
我找到的大多数能够在JavaScript中完成此操作的软件似乎都使用JavaScript BigInt库（http://www.leemon.com/crypto/BigInt.html）。使用此库进行单个如此大的指数运算需要大约9秒钟，在我的慢浏览器（Firefox 3.0与SpiderMonkey）上。我正在寻找至少快10倍的解决方案。明显的想法是使用平方乘（通过平方进行指数运算，http://en.wikipedia.org/wiki/Exponentiation_by_squaring），但对于2048位的数字来说太慢了：它需要多达4096次乘法。
升级浏览器不是一个选项。使用另一种编程语言也不是一个选项。将数字发送到Web服务也不是一个选项。
是否有更快的替代方法实现？
更新：按照outis下面回答中提到的文章http://www.ccrwest.org/gordon/fast.pdf建议，通过进行一些额外的准备工作（即预先计算几百个幂），可以仅使用最多354次模乘法来进行2048位模指数运算。（传统的平方-乘法方法速度较慢：最多使用4096次模乘法。）这样做可以在Firefox 3.0中将模指数运算加速6倍，在Google Chrome中加速4倍。之所以没有获得完整的4096/354加速比，是因为BigInt的模指数算法已经比平方-乘法更快，因为它使用Montgomery约简算法（http://en.wikipedia.org/wiki/Montgomery_reduction）。
更新：从BigInt的代码开始，似乎值得进行两级手动优化（和内联）Karatsuba乘法（http://en.wikipedia.org/wiki/Karatsuba_algorithm），然后再转换为BigInt中实现的基于32768的O(n^2)乘法。这将使2048位整数的乘法加速2.25倍。不幸的是，模操作并没有变得更快。
更新：使用在http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf中定义的修改过的Barrett约简和Karatsuba乘法以及预先计算幂（如http://www.ccrwest.org/gordon/fast.pdf中所定义的），我可以将单次乘法所需的时间从73秒降至12.3秒，在Firefox 3.0中。这似乎是我能做到的最好，但仍然太慢了。
更新：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）解释器不值得使用，因为它的速度几乎与Firefox 3.0中的JavaScript相同。
更新：Flash Player 10中的ActionScript 3（AS3）解释器，如果使用int而不是Number，并且使用Vector.而不是Array，则比Firefox 3.0中的JavaScript解释器快高达6.5倍。至少在2048位大整数乘法方面，速度提高了2.41倍。因此，如果可以，在AS3中执行模指数运算并在Flash Player 10中执行可能是值得的。请注意，这仍然比Google Chrome的JavaScript解释器V8慢。有关各种编程语言和JavaScript实现的速度比较，请参见http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html。
更新：有一个非常快的Java解决方案，如果安装了Java插件，则可以从浏览器的JavaScript中调用它。以下解决方案比使用BigInt的纯JavaScript实现快约310倍。
(g^x) mod p，其中^是指数运算，mod是模运算。所有输入都是非负整数，x大约有256位，p是一个2048位的质数，g可能有多达2048位。我找到的大多数能够在JavaScript中完成此操作的软件似乎都使用JavaScript BigInt库（http://www.leemon.com/crypto/BigInt.html）。使用此库进行单个如此大的指数运算需要大约9秒钟，在我的慢浏览器（Firefox 3.0与SpiderMonkey）上。我正在寻找至少快10倍的解决方案。明显的想法是使用平方乘（通过平方进行指数运算，http://en.wikipedia.org/wiki/Exponentiation_by_squaring），但对于2048位的数字来说太慢了：它需要多达4096次乘法。
升级浏览器不是一个选项。使用另一种编程语言也不是一个选项。将数字发送到Web服务也不是一个选项。
是否有更快的替代方法实现？
更新：按照outis下面回答中提到的文章http://www.ccrwest.org/gordon/fast.pdf建议，通过进行一些额外的准备工作（即预先计算几百个幂），可以仅使用最多354次模乘法来进行2048位模指数运算。（传统的平方-乘法方法速度较慢：最多使用4096次模乘法。）这样做可以在Firefox 3.0中将模指数运算加速6倍，在Google Chrome中加速4倍。之所以没有获得完整的4096/354加速比，是因为BigInt的模指数算法已经比平方-乘法更快，因为它使用Montgomery约简算法（http://en.wikipedia.org/wiki/Montgomery_reduction）。
更新：从BigInt的代码开始，似乎值得进行两级手动优化（和内联）Karatsuba乘法（http://en.wikipedia.org/wiki/Karatsuba_algorithm），然后再转换为BigInt中实现的基于32768的O(n^2)乘法。这将使2048位整数的乘法加速2.25倍。不幸的是，模操作并没有变得更快。
更新：使用在http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf中定义的修改过的Barrett约简和Karatsuba乘法以及预先计算幂（如http://www.ccrwest.org/gordon/fast.pdf中所定义的），我可以将单次乘法所需的时间从73秒降至12.3秒，在Firefox 3.0中。这似乎是我能做到的最好，但仍然太慢了。
更新：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）解释器不值得使用，因为它的速度几乎与Firefox 3.0中的JavaScript相同。
更新：Flash Player 10中的ActionScript 3（AS3）解释器，如果使用int而不是Number，并且使用Vector.而不是Array，则比Firefox 3.0中的JavaScript解释器快高达6.5倍。至少在2048位大整数乘法方面，速度提高了2.41倍。因此，如果可以，在AS3中执行模指数运算并在Flash Player 10中执行可能是值得的。请注意，这仍然比Google 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＃）吗？
Cedar Mill/ AMDWindsor或类似的处理器？我很想看到这个问题最初提出的解决方案：SpiderMonkey 1.8是否有可能在该硬件上及时评估该数学问题。 - JamesTheAwesomeDude