{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.manongdao.com/data/attach/logo/logo.png', '推荐 Lonely孤独者° 的问题《Fastest modular exponentiation in JavaScript》','https://www.manongdao.com/q-464858.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
My problem is to compute (g^x) mod p quickly in JavaScript, where ^ is exponentiation, mod is the modulo operation. All inputs are nonnegative integers, x has about 256 bits, and p is a prime number of 2048 bits, and g may have up to 2048 bits.
Most of the software I've found that can do this in JavaScript seems to use the JavaScript BigInt library (http://www.leemon.com/crypto/BigInt.html). Doing a single exponentiation of such size with this library takes about 9 seconds on my slow browser (Firefox 3.0 with SpiderMonkey). I'm looking for a solution which is at least 10 times faster. The obvious idea of using square-and-multiply (exponentiation by squaring, http://en.wikipedia.org/wiki/Exponentiation_by_squaring) is too slow for 2048-bit numbers: it needs up to 4096 multiplications.
Upgrading the browser is not an option. Using another programming language is not an option. Sending the numbers to a web service is not an option.
Is there a faster alternative implemented?
Update: By doing some extra preparations (i.e. precomputing a few hundred powers) as recommended by the article http://www.ccrwest.org/gordon/fast.pdf mentioned in outis' answer below, it is possible do to a 2048-bit modular exponentiation using only at most 354 modular multiplications. (The traditional square-and-multiply method is much slower: it uses maximum 4096 modular multiplications.) Doing so speeds up the modular exponentiation by a factor of 6 in Firefox 3.0, and by a factor of 4 in Google Chrome. The reason why we are not getting the full speedup of 4096/354 is that BigInt's modular exponentation algorithm is already faster than square-and-multiply, because it uses Montgomery reduction (http://en.wikipedia.org/wiki/Montgomery_reduction).
Update: Starting from BigInt's code, it seems worthwhile doing two levels of hand-optimized (and inlined) Karatsuba multiplication (http://en.wikipedia.org/wiki/Karatsuba_algorithm), and only then revert to the base-32768 O(n^2) multiplication implemented in BigInt. This speeds up multiplications by a factor of 2.25 for 2048-bit integers. Unfortunately, the modulo operation does not become faster.
Update: Using the modified Barrett reduction defined in http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf and Karatsuba multiplication and precomputing powers (as defined in http://www.ccrwest.org/gordon/fast.pdf), I can get down the time needed for a single multiplication from 73 seconds to 12.3 seconds in Firefox 3.0. This seems to be the best I can do, but it is still too slow.
Update: The ActionScript 2 (AS2) interpreter in the Flash Player isn't worth using, because it seems to be slower than the JavaScript interpreter in Firefox 3.0: for Flash Player 9, it seems to be 4.2 times slower, and for Flash Player 10, it seems to be 2.35 times slower. Does anybody know the speed difference between ActionScript2 and ActionScript3 (AS3) for number chrunching?
Update: The ActionScript 3 (AS3) interpreter in Flash Player 9 isn't worth using because it has just about the same speed as the JavaScript int Firefox 3.0.
Update: The ActionScript 3 (AS3) interpreter in Flash Player 10 can be up to 6.5 times faster than the JavaScript interpreter in Firefox 3.0 if int is used instead of Number, and Vector.<int> is used instead of Array. At least it was 2.41 times faster for 2048-bit big integer multiplication. So it might be worth doing the modular exponentiation in AS3, executing it in Flash Player 10 if available. Please note that this is still slower than V8, the JavaScript interpreter of Google Chrome. See http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html for a speed comparison of various programming language and JavaScript implementations.
Update: There is a very fast Java solution, which can be called from the browser's JavaScript if the Java plugin is installed. The following solution is about 310 times faster than the pure JavaScript implementation using BigInt.
<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>
Can anyone translate this code to Silverlight (C#)?
I'd love to see the source code to your modified BigInt library - is it available anywhere?
Would some other client side technology that's callable from JS, such as a Java applet or Flash movie, be acceptable? BigInt's approach is already fairly fast. You can tweak BigInt, or you can try a different algorithm, but you probably won't get an order of magnitude improvement.
Why not do it server side in some kind of web service using a more appropriate language like C? Times will then be time for one round trip (less than 9 seconds), plus the time for the server to calculate the result using some BigInt library in native code. This is likely to be much faster.
I use "%" for modular (mod) and "/" for integer division. Let function f(p,g,x,r) calculate (r*g^x)%p on the condition that r<p and g<p. f() can be implemented as:
This routine involves a little more calculation, but each integer is less than 4096 bits which is usually much smaller than g^x. I believe this could be more efficient than the direct calculation. Also note that g^(x%i) can be calculated in a faster manner because we have calculated g^(i+1).
EDIT: see this post. Mehrdad gives the right (and better) solution.
Try this Montgomery modular reduction from http://code.google.com/p/bi2php/ on JavaScript.