我的问题是计算 (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＃）吗？