admin管理员组文章数量:1201976
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 (.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, ) 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 .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 ().
Update: Starting from BigInt's code, it seems worthwhile doing two levels of hand-optimized (and inlined) Karatsuba multiplication (), 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 .pdf and Karatsuba multiplication and precomputing powers (as defined in .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 .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#)?
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#)?
Share Improve this question edited Oct 4, 2009 at 19:17 pts asked Sep 20, 2009 at 8:48 ptspts 87.2k23 gold badges115 silver badges197 bronze badges 2 |5 Answers
Reset to default 4Would some other client side technology that's callable from JS, such as a Java applet or Flash movie, be acceptable? Leemon's implementation (based on Montgomery Reduction) 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.
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:
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
}
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.
The question as originally stated is no longer applicable, but this thread still floats to the top of Google even today for JavaScript programmers searching for the modular exponentiation algorithm.
There are multiple ways to do it ranging from a naive multiply-reduce loop to bit-twiddling magick; here's one based on the so-called "binary right-to-left method", which splits the difference between being performant and being a readable reference implementation:
function bn_powMod(a, e, m) {
// h/t https://umaranis.com/2018/07/12/calculate-modular-exponentiation-powermod-in-javascript-ap-n/
if (m === 1n)
return 0n;
if (e < 0n)
return bn_powMod(bn_modInv(a, m), -e, m);
for (var b = 1n; e; e >>= 1n) {
if (e % 2n === 1n)
b = (b * a) % m;
a = (a * a) % m;
}
return b;
}
function bn_modInv(a, m) {
// h/t https://github.com/python/cpython/blob/v3.8.0/Objects/longobject.c#L4184
const m0 = m;
var b = 1n, c = 0n, q, r;
while (m) {
[q, r] = [a/m, a%m];
[a, b, c, m] = [m, c, b - q*c, r];
}
if (a !== 1n)
throw new RangeError("Not invertible");
if (b < 0n)
b += m0;
return b;
}
If you're looking for actually performant solutions, you might try Stanford's sjcl.bn.montpowermod, npm's modular-power, or Pomcor's pjclMontExp; the last of these options does not base off ES6 BigInts and was apparently designed for high performance under constraint, so it might be a candidate even for older browsers on underpowered hardware.
If you've found this thread because you're rolling your own in-browser RSA-based cryptography, please remember that timing attacks and an infinite variety of implementation attacks exist, and consider using something more prepackaged.
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.
Try this Montgomery modular reduction from http://code.google.com/p/bi2php/ on JavaScript.
本文标签： primesFastest modular exponentiation in JavaScriptStack Overflow
版权声明：本文标题：primes - Fastest modular exponentiation in JavaScript - Stack Overflow 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/web/1738637255a2104108.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
Cedar Mill/ AMDWindsor, or thereabouts? I would be interested to see a resolution to the question as originally asked: whether SpiderMonkey 1.8 has the potential to evaluate that math in a timely manner on that hardware – JamesTheAwesomeDude Commented Sep 22, 2022 at 19:33