Source of “adbabBigint.js”.
1288 lines, 38.8 KBytes.   Last modified 6:34 pm, 22nd November 2015 PST.
1 // Emacs settings: -*- mode: Fundamental; tab-width: 4; -*- 2 3 //////////////////////////////////////////////////////////////////////////// 4 // // 5 // Javascript unlimited-magnitude integers // 6 // // 7 // Copyright (c) 2009-2013, Andrew Birrell // 8 // Do not use except within pages of the "birrell.org" web server // 9 // // 10 //////////////////////////////////////////////////////////////////////////// 11 12 // This library implements arithmetic on integers of unlimited magnitude in 13 // Javascript, including support for negative integers and NaN. It includes 14 // basic arithmetic, modular arithmetic, and a few number theory operations 15 // (GCD, modular inverse, prime generation, and primality testing). 16 // 17 // The library creates the global "adbab.Bigint" class (creating "adbab" if 18 // needed). 19 // 20 // Bigints are represented as objects containing a vector of positive 21 // integers, each integer < radix, together with a sign bit and a "NaN" 22 // flag. The objects are immutable, except while being created during an 23 // operation. 24 // 25 // The public entry points are as follows. See the source for more detail. 26 // 27 // Constructor: 28 // new Bigint(x) ... create a Bigint object from a Number or String 29 // Properties of a Bigint object "a" (read-only); 30 // a.neg: ... a boolean saying whether the number is negated 31 // a.NaN: ... iff true or a string, the number is NaN 32 // a.v ... the digits of "a", but undefined if a is NaN 33 // Methods of a Bigint object "a": 34 // a.toString() ... a string for "a"; a.toString(true) does hex 35 // a.absComp(b) ... (-1, 0, +1) if |a| is (lt, eq, gt) |b| 36 // a.compare(b) ... (-1, 0, +1) if a is (lt, eq, gt) b 37 // a.negate() ... -a 38 // a.add(b) ... a + b 39 // a.sub(b) ... a - b 40 // a.div(b) ... a / b, rounding towards 0 41 // a.mod(b) ... a MOD b = a - b * (a/b). This can be negative. 42 // a.mul(b) ... a * b 43 // a.mul(b, m) ... (a * b) MOD m 44 // a.mulInt(n) ... a * n for ordinary positive integer n 45 // a.pow(b) ... a ^ b 46 // a.pow(b, m) ... (a ^ b) MOD m 47 // a.gcd(b) ... gcd(|a|, |b|) 48 // a.inverse(b) ... c s.t. (a * c) MOD b = 1; requires gcd(a, b) = 1 49 // a.randomLT() ... a random number in [0 .. |a|-1] 50 // a.isPrime() ... true iff a is probably prime (1 in 2^80) 51 // Static properties of "Bigint" (read-only): 52 // Bigint.zero ... = new Bigint(0) 53 // Bigint.one ... = new Bigint(1) 54 // Bigint.two ... = new Bigint(2) 55 // Static methods of "Bigint" (where "n" is an ordinary positive integer): 56 // Bigint.randomInt(n) ... a random ordinary integer in [0..n-1] 57 // Bigint.random(n) ... a random number in [0 .. 2^n-1] 58 // Bigint.prime(n) ... a random probable prime in [2^(n-1) .. 2^n-1] 59 // 60 // Note that the "randomLT", "random", and "prime" methods use "randomInt" 61 // for their randomness. "randomInt" uses "Math.random", which does not 62 // produce cryptographically secure random numbers. Anyone who cares should 63 // replace the "randomInt" method with something better. 64 // 65 // There is also a lower-level set of functions, working with sub-array 66 // objects {v, start, len}, with no allowance for NaN or sign. These are 67 // more efficent than the Bigint methods, but more difficult to use. The 68 // client is responsible for buffer management and mutability. 69 // 70 // a.toV(clone) ... the sub-array for "a", using a.v or a new array 71 // Bigint.subArray ... the sub-array functions; see individual comments 72 // 73 // In general, the semantics mirror the fine print of EcmaScript Number 74 // semantics, except for the omission of infinity and negative zero: 75 // 76 // - errors are converted into "NaN"; the "NaN" flag is a relevant string; 77 // - "NaN" propagates through most operations, except that NaN.pow(0)=1; 78 // - the Bigint constructor behaves like "Number(x)" for all x; 79 // - division rounds towards zero (sadly); 80 // - remainder = dividend - quotient * divisor (and so can be negative). 81 // 82 // Non-modular "pow" returns a NaN if the computation is infeasible. 83 // 84 // Overall, the performance is pretty good, for Javascript. For example, 85 // "a^b mod m" with 2048-bit numbers takes about 260 milliseconds on a 1.2 86 // GHz 2-core Intel Core M Macbook with Safari 9. (If m = pq, as in RSA, 87 // then using the Chinese Remainder theorem for the same calculation reduces 88 // the time to about 75 milliseconds.) 89 // 90 // The basic algorithms used here are very simple: schoolroom add, subtract, 91 // multiply, and long division. Exponentiation is k-ary sliding window. 92 // Primality testing is Miller-Rabin, preceded by deterministic tests for 93 // small numbers. The code uses Karatsuba multiplication when it seems 94 // useful. The code includes Montgomery reduction, but doesn't use it. 95 // 96 // This library is copyright, and all rights are reserved. You may read it 97 // for educational purposes, but you may not otherwise use it except 98 // implicitly in web pages served by the "birrell.org" web server. Even 99 // then, the library is provided "as is" with no warranty whatsoever. 100 // 101 // Don't use this library to protect anything of value. 102 103 "use strict"; 104 105 var adbab; if (typeof adbab == "undefined") adbab = {}; 106 107 adbab.Bigint = (function() { // in-place call of an anonymous function 108 // 109 // This creates the BigInt class and returns its constructor function. 110 // The declarations are in a local scope: the global namespace is not 111 // altered. 112 113 var radix = 64*1024*1024; 114 // As coded below, we require exact representation of integers up to 115 // 2*(radix*radix-1) ... see the inner loop of "bigMulClassicV". 116 // 117 // EcmaScript represents numbers as 64-bit IEEE floats, with exact 118 // integers up to 2^53 (roughly 9 * 10^15). That allows radix 2^26. 119 // 120 // "bigPowSlidingV" relies on "radix" being a power of 2, and < 2^32 121 // (by an amount depending on its "k" tuning parameter). 122 // 123 var radixBits = 26; 124 // radix == 2 ^ radixBits; for "bigPowSlidingV" and Miller-Rabin. 125 126 var verify = false; // a debugging aid 127 128 function Bigint(n) { 129 // Constructor for a Bigint with given value. 130 // 131 // Literals are by default decimal, but are hex if they contain 132 // [a-f] or if the are prefixed by "0x". Non-numeric strings create 133 // NaN with the string as the NaN value, so are useful for 134 // propagating error messages. 135 // 136 // The Bigint object itself (not instantiations from "new Bigint") 137 // has a few properties and methods available globally, e.g., 138 // Bigint.zero and Bigint.random; these are all intended to be 139 // read-only. 140 // 141 this.neg = false; 142 if (n === 0 || n === false || n === null || n === "") { 143 // Values that map to 0 144 var v = []; 145 v.push(0); 146 this.v = v; 147 } else if (!n) { 148 // Values that map to NaN: the number "NaN" and undefined 149 this.NaN = true; 150 } else if (typeof(n) == "number" || typeof(n) == "boolean") { 151 // Native number, or boolean "true" converted implicitly. 152 if (n < 0) { 153 this.neg = true; 154 n = -n; 155 } 156 var v = []; 157 while (n > 0) { 158 var n2 = Math.floor(n / radix); // n can be > 31 bits 159 v.push(n - n2 * radix); 160 n = n2; 161 } 162 if (v.length === 0) v.push(0); 163 this.v = v; 164 } else { 165 // String, Object, Function, and anything not in EcmaScript. 166 if (typeof(n) == "string") { 167 var nSp = n.replace(" ", ""); 168 if (nSp.length > 0 && nSp.charAt(0) == "-") { 169 nSp = nSp.substr(1, nSp.length); 170 this.neg = true; 171 } 172 var base; 173 if (nSp.match(/^[0-9]+$/)) { 174 base = 10; 175 } else if (nSp.match(/^[0-9a-f]+$/i)) { 176 base = 16; 177 } else if (nSp.match(/^0x[0-9a-f]+$/i)) { 178 base = 16; 179 nSp = nSp.substr(2, nSp.length); 180 } else { 181 base = 0; 182 this.NaN = n; 183 } 184 if (base > 0) { 185 var temp = null; 186 for (var i = 0; i < nSp.length; i++) { 187 var c = nSp.charAt(i); 188 if (c != " ") { 189 var next = new Bigint(parseInt(c, base)); 190 temp = (temp ? temp.mulInt(base).add(next) : 191 next); 192 } 193 } 194 this.v = temp.v; 195 } 196 } else { 197 this.NaN = "syntax error in constant"; 198 } 199 } 200 } 201 202 Bigint.prototype.normalize = function bigNormalize() { 203 // Remove leading zeros, retaining one for exactly 0, and avoid 204 // negative 0. 205 // 206 var v = this.v; 207 var limit = v.length-1; 208 for (var i = limit; i > 0; i--) if (v[i]) break; 209 if (i < limit) v.length = i + 1; 210 if (v.length == 1 && v[0] === 0) this.neg = false; 211 }; 212 213 214 // 215 // Sub-array functions: available through Bigint.subArray 216 // 217 218 Bigint.prototype.toV = function bigToV(clone) { 219 // create a sub-array object from this Bigint, using the same 220 // array or a new one, depending on "clone". 221 // 222 var av = this.v; 223 return {v: (clone ? av.slice(0) : av), start: 0, len: av.length}; 224 } 225 226 function bigScratchV() { 227 // create a sub-array object with empty contents. 228 // 229 return {v: [], start: 0, len: 0}; 230 } 231 232 function bigLenV(a) { 233 // return the length sub-array "a" would have with leading 234 // zeros removed (but leaving a single 0 for exactly 0). 235 // 236 var av = a.v; 237 var len = a.len; 238 var as = a.start + a.len; 239 while (len > 1 && av[--as] === 0) len--; 240 return len; 241 } 242 243 function bigFromV(a, neg) { 244 // create a Bigint from sub-array "a". 245 // 246 // Checks that a.start is 0, which it always is; if not we could use 247 // Array.slice, but we never need to. 248 // 249 var res = new Bigint(); 250 res.NaN = false; 251 if (a.start !== 0) alert("bigFromV: start is " + a.start); 252 res.v = a.v; 253 res.v.length = bigLenV(a); 254 res.neg = neg; 255 res.normalize(); 256 return res; 257 } 258 259 260 // Compare, Add, Subtract ... 261 262 function bigCompareV(a, b) { 263 // return (-1, 0, +1) as sub-array "a" (<, =, >) "b". 264 // 265 var av = a.v, bv = b.v; 266 var aLen = a.len; 267 var bLen = b.len; 268 var as = a.start + aLen, bs = b.start + bLen; 269 for (; aLen > bLen; aLen--) if (av[--as] > 0) return 1; 270 for (; bLen > aLen; bLen--) if (bv[--bs] > 0) return -1; 271 // now aLen == bLen 272 while (aLen-- > 0) { 273 var an = av[--as], bn = bv[--bs]; 274 if (an < bn) return -1; 275 if (an > bn) return 1; 276 } 277 return 0; 278 } 279 280 function bigAddV(a, b, c, k) { 281 // for sub-arrays a, b, and integer k, store a + b*k in c. 282 // 283 // "k === undefined" is treated as 1. Requires 0 <= k < radix. 284 // 285 // "c" can be the same object as "a" and/or "b". 286 // 287 var av = a.v, bv = b.v, cv = c.v; 288 if (!k && k !== 0) k = 1; 289 var carry = 0; 290 var as = a.start, bs = b.start, cs = c.start; 291 for (var limit = cs + (a.len < b.len ? a.len : b.len); 292 cs < limit;) { 293 var n = av[as++] + k * bv[bs++] + carry; 294 carry = (n/radix) | 0; 295 cv[cs++] = n - carry * radix; 296 } 297 // if (a.len > b.len) ... 298 for (var limit = a.start + a.len; as < limit; ) { 299 var n = av[as++] + carry; 300 carry = (n/radix) | 0; 301 cv[cs++] = n - carry * radix; 302 } 303 // if (b.len > a.len) ... 304 for (var limit = b.start + b.len; bs < limit; ) { 305 var n = k * bv[bs++] + carry; 306 carry = (n/radix) | 0; 307 cv[cs++] = n - carry * radix; 308 } 309 if (carry > 0) cv[cs++] = carry; 310 c.len = cs - c.start; 311 } 312 313 function bigSubV(a, b, c, k) { 314 // for sub-arrays a, b, and integer k, if a >= b*k, store a - b*k in 315 // c and return true. Otherwise return false; in this case, 316 // c will be changed in a way suitable for bigDivmodV. 317 // 318 // "k === undefined" is treated as 1. Requires 0 <= k < radix. 319 // 320 // Does not remove leading zeros. 321 // 322 // "c" can be the same object as "a" and/or "b". 323 // 324 var av = a.v, bv = b.v, cv = c.v; 325 if (b.len > a.len) return false; // too big; simplifies later code 326 if (!k && k !== 0) k = 1; 327 var carry = 0; 328 var as = a.start, bs = b.start, cs = c.start; 329 for (var limit = a.start + b.len; as < limit; ) { 330 var n = av[as++] - bv[bs++] * k + carry; 331 // Math.floor can be slow, so we use a bitwise "or". But n can 332 // be negative and toInt32 rounds to 0, so we bias by "radix" 333 // briefly. 334 carry = (((n/radix) + radix) | 0) - radix; 335 cv[cs++] = n - carry * radix; 336 } 337 for (var limit = a.start + a.len; as < limit; ) { 338 var n = av[as++] + carry; 339 carry = (((n/radix) + radix) | 0) - radix; // see comment above 340 cv[cs++] = n - carry * radix; 341 } 342 if (carry < 0) { 343 cv[cs++] = carry; 344 c.len = a.len + 1; 345 return false; 346 } else { 347 c.len = a.len; 348 return true; 349 } 350 } 351 352 353 // Classical division ... 354 355 function bigDivIntV(a, k, q) { 356 // divide sub-array "a" by integer k and return the remainder. 357 // If "q", place the quotient in q. Requires 0 < k < radix. 358 // 359 // Does not remove leading zeros. 360 // 361 // "q" can be the same object as "a". 362 // 363 var rem = 0; 364 for (var i = a.len-1; i >= 0; i--) { 365 var n = rem * radix + a.v[a.start + i]; 366 var quotient = (n/k) | 0; 367 rem = n - quotient * k; 368 if (q) q.v[q.start + i] = quotient; 369 } 370 if (q) q.len = a.len; 371 return rem; 372 } 373 374 function bigDivmodV(a, b, q) { 375 // compute sub-array a/b and a mod b. Place a mod b into a. 376 // If "q", place the quotient in q. Requires b > 0. 377 // 378 // We use classic shift/test/subtract long division, but with a 379 // better estimate for the next quotient digit. (With thanks to 380 // Donald Knuth.) Note that by using three dividend digits, we need 381 // no normalization. 382 // 383 var av = a.v; 384 var bLen = bigLenV(b); 385 if (a.len < bLen) { // the quotient is 0, the remainder is just "a". 386 if (q) { 387 q.v[q.start] = 0; 388 q.len = 1; 389 } 390 } else if (bLen == 1) { // short division, single digit remainder 391 av[a.start] = bigDivIntV(a, b.v[b.start], q); 392 a.len = 1; 393 if (q) q.len = bigLenV(q); 394 } else { 395 // "b" has at least two digits, and "a" has at least as many as 396 // "b" 397 var topB = b.v[b.start + bLen-1]; 398 var msb = topB * radix + b.v[b.start + bLen-2]; 399 var qLen = 1 + a.len - bLen; 400 var d = {v: av, start: 0, len: 0}; 401 var first = true; // fake the insertion of a leading zero in "a" 402 for (var e = qLen - 1; e >= 0; e--) { 403 d.start = a.start + e; 404 d.len = a.len - e; 405 var dsb = d.start + bLen; 406 var qDigit = ( 407 (((first ? 0 : av[dsb]) * radix + av[dsb - 1]) * radix + 408 av[dsb - 2]) 409 / msb) | 0; 410 if (qDigit > 0 && !bigSubV(d, b, d, qDigit)) { 411 // rare: qDigit can estimate high by one or two (only) 412 while (d.v[d.start + d.len-1] < 0) { 413 bigAddV(d, b, d); 414 qDigit--; 415 } 416 } else if ((av[dsb] > 0 || av[dsb - 1] >= topB) && 417 bigCompareV(d, b) >= 0) { 418 // very rare: compensate for a rounding error in qDigit. 419 // (optimized to avoid calling bigCompareV too much) 420 bigSubV(d, b, d); 421 qDigit++; 422 if (bigCompareV(d, b) >= 0) alert("Bug in bigDivmodV"); 423 } 424 if (q) q.v[q.start + e] = qDigit; 425 if (first) { first = false; } else { a.len--; } 426 } 427 a.len = bigLenV(a); 428 if (q) { 429 q.len = qLen; 430 q.len = bigLenV(q); 431 } 432 } 433 } 434 435 436 // Montgomery reduction ... 437 438 function inverseN(n) { 439 // For odd n, and 0 < n < radix, returns -inverse(n, radix). 440 // Assumes that radix is a power of two. 441 // 442 // Theorem: if inverse(n, p) = y and p mod q = 0, then 443 // inverse(n, pq) = y * (2-ny) mod pq. (With thanks to Tom Wu.) 444 // 445 var y = 1; 446 for (var p = 4; p < radix; p = p*p) { 447 y = (y * ((2-n*y) & (p-1))) & (p-1); 448 } 449 y = (y * ((2-n*y) % radix)) % radix; 450 return (y > 0 ? radix-y : -y); 451 } 452 453 function Montgomery(m) { 454 // Constructor for Montgomery reduction mod m, for sub-array "m". 455 // 456 // Assumes that m is odd and radix is a power of two. 457 // 458 this.modulus = m; 459 this.temp = bigScratchV(); 460 this.inverseM = inverseN(m.v[m.start]); 461 } 462 463 Montgomery.prototype.verify1 = function verify1(a, c) { 464 // Verify the Montgomery "prepare" step 465 // 466 var t = bigScratchV(); 467 var t2 = bigScratchV(); 468 for (var i = 0; i < a.len; i++) t2.v[t2.start+i] = a.v[a.start+i]; 469 t2.len = bigLenV(a.len); 470 bigDivModV(t2, this.modulus, false); 471 verify = false; // avoid infinite recursion 472 this.reduce(c, t); 473 verify = true; 474 if (bigCompareV(t2, t) !== 0) { 475 alert("Bug in Montgomery prepare"); 476 } 477 }; 478 479 Montgomery.prototype.verify2 = function verify2(a, c) { 480 // Verify the Montgomery "reduce" step 481 // 482 var t2 = bigScratchV(); 483 for (var i = 0; i < a.len; i++) t2.v[t2.start+i] = a.v[a.start+i]; 484 t2.len = bigLenV(a.len); 485 bigDivModV(t2, this.modulus, false); 486 verify = false; // avoid infinite recursion 487 var t = this.prepare(c); 488 verify = true; 489 if (bigCompareV(t2, t) !== 0) { 490 alert("Bug in Montgomery reduce"); 491 } 492 }; 493 494 Montgomery.prototype.prepare = function mPrepare(a) { 495 // For sub-array "a", return a * R mod m 496 // 497 var c = bigScratchV(); 498 var av = a.v, cv = c.v; 499 var cs = c.start; 500 for (var limit = cs + this.modulus.len; cs < limit;) cv[cs++] = 0; 501 var as = a.start; 502 for (var limit = cs + a.len; cs < limit;) cv[cs++] = av[as++]; 503 c.len = cs - c.start; 504 bigDivmodV(c, this.modulus, false); 505 if (verify) this.verify1(a, c); 506 return c; 507 }; 508 509 Montgomery.prototype.reduce = function mReduce(a, c) { 510 // For sub-array "a", with a < mR, set c to a * R^-1 mod m. 511 // 512 // Handbook of Applied Cryptography, algorithm 14.32 513 // 514 var m = this.modulus; 515 var mLen = m.len; 516 var inverseM = this.inverseM; 517 var av = a.v, cv = c.v; 518 var as = a.start, cs = c.start; 519 for (var limit = as + a.len; as < limit;) cv[cs++] = av[as++]; 520 c.len = a.len; 521 for (var i = 0; i < mLen; i++) { 522 var u = cv[c.start + i] * inverseM % radix; 523 var d = {v: cv, start: c.start + i, len: c.len - i}; 524 bigAddV(d, m, d, u); // c = c + u * m * radix^i 525 c.len = d.len + i; 526 } 527 // c = c / radix^mLen ... 528 cs = c.start; 529 for (var csm = c.start+mLen; csm < c.start+c.len;) { 530 cv[cs++] = cv[csm++]; 531 } 532 c.len -= mLen; 533 // c = c mod m, given that c < 2m ... 534 if (bigCompareV(c, m) >= 0) bigSubV(c, m, c); 535 c.len = bigLenV(c); 536 if (verify) this.verify2(a, c); 537 }; 538 539 Montgomery.prototype.multiply = function mMultiply(a, b, c) { 540 // For sub-arrays "a" and "b", set c to a * b * R^-1 mod m 541 // 542 // We could use Handbook of Applied Cryptography, algorithm 14.36. 543 // But profiling indicates that we'd gain less than 10% overall, and 544 // perhaps nothing, compared with not using Montgomery at all. 545 // Using Montgomery reduction by itself is distinctly slower, so 546 // this function is currently not used (but it has been debugged). 547 // 548 var ab = this.temp; 549 bigMulKV(a, b, ab); 550 ab.len = bigLenV(ab); 551 this.reduce(ab, c); 552 }; 553 554 555 // Multiplication ... 556 557 function bigMulIntV(a, k, c) { 558 // multiply sub-array "a" by integer k and place the result in c. 559 // Requires 0 <= k < radix. 560 // 561 // "c" can be the same object as "a". 562 // 563 var av = a.v, cv = c.v; 564 var as = a.start, cs = c.start; 565 var carry = 0; 566 for (var limit = as + a.len; as < limit;) { 567 var n = k * av[as++] + carry; 568 carry = (n/radix) | 0; 569 cv[cs++] = n - carry * radix; 570 } 571 if (carry > 0) cv[cs++] = carry; 572 c.len = cs - c.start; 573 } 574 575 function bigMulClassicV(a, b, c) { 576 // INTERNAL: multiply sub-array "a" by "b", placing result in "c". 577 // 578 // Sets c.len = a.len + b.len, even if this includes a leading zero. 579 // 580 // This version is classic paper-and-pencil long multiplication, 581 // with some optimization and a special-case for squaring. 582 // 583 if (a == b) { // squaring 584 var av = a.v, cv = c.v; 585 var as = a.start, cs = c.start; 586 c.len = 2 * a.len; 587 for (var i = 0, limit = a.len; i < limit; i++, cs++) { 588 var m = av[as++]; 589 var carry = 0; 590 var asj = a.start, csj = cs; 591 for (var j = 0; j < i; j++, csj++) { 592 var n = 2 * m * av[asj++] + cv[csj] + carry; 593 carry = (n/radix) | 0; // ">>>" requires n < 2**32 594 cv[csj] = n - carry * radix; 595 } 596 // Do the diagonal 597 var n = m * m + carry; 598 carry = (n/radix) | 0; 599 cv[cs+i] = n - carry * radix; 600 cv[cs+i+1] = carry; 601 } 602 } else { 603 var big = (a.len >= b.len ? a : b); 604 var small = (big == a ? b : a); 605 var limB = big.len; 606 var limS = small.len; 607 var bigv = big.v, smallv = small.v, cv = c.v; 608 var bs = big.start, ss = small.start, cs = c.start; 609 c.len = a.len + b.len; 610 for (var i = 0; i < limS; i++, cs++) { 611 var nBig = bigv[bs++]; 612 var nSmall = smallv[ss++]; 613 var carry = 0; 614 var bsj = big.start, ssj = small.start, csj = cs; 615 for (var j = 0; j < i; j++, csj++) { 616 var n = nBig * smallv[ssj++] + nSmall * bigv[bsj++] + 617 cv[csj] + carry; 618 // Note: "n" can reach 2*(radix*radix-1) 619 carry = (n/radix) | 0; // ">>>" requires n < 2**32 620 cv[csj] = n - carry * radix; 621 } 622 // Do the diagonal 623 var n = nBig * nSmall + carry; 624 carry = (n/radix) | 0; 625 cv[cs+i] = n - carry * radix; 626 cv[cs+i+1] = carry; 627 } 628 for (var i = limS; i < limB; i++, cs++) { 629 // var nBig = bigv[bs++]; 630 // The above line provokes an obscure bug in Safari 5.1.8 on OS X 10.6.8 631 var nBig = bigv[big.start+i]; 632 var carry = 0; 633 var ssj = small.start, csj = cs; 634 for (var j = 0; j < limS; j++, csj++) { 635 var n = cv[csj] + nBig * smallv[ssj++] + carry; 636 carry = (n/radix) | 0; 637 cv[csj] = n - carry * radix; 638 } 639 cv[cs+small.len] = carry; 640 } 641 } 642 } 643 644 function bigMulKV(a, b, c) { 645 // INTERNAL: same signature and semantics as bigMulClassicV, but 646 // using the Karatsuba algorithm. 647 // 648 var halfA = a.len >>> 1, halfB = b.len >>> 1; 649 var half = (halfA > halfB ? halfA : halfB); 650 if (half < 40) return bigMulClassicV(a, b, c); 651 var lsA = {v: a.v, start: a.start, len: half}; 652 var msA = {v: a.v, start: a.start + half, len: a.len - half}; 653 var lsB = (a == b ? lsA : 654 {v: b.v, start: b.start, len: half}); 655 var msB = (a == b ? msA : 656 {v: b.v, start: b.start + half, len: b.len - half}); 657 var s = {v: c.v, start: c.start + a.len + b.len}; 658 // Caution: recursive calls of bigMulKV also use scratch space 659 if (half >= a.len) { 660 // "a" is too short: there's nothing to gain 661 bigMulKV(a, lsB, c); 662 bigMulKV(a, msB, s); 663 var c1 = {v: c.v, start: c.start+half, len: c.len-half}; 664 bigAddV(c1, s, c1); 665 c.len = a.len + b.len; 666 } else if (half >= b.len) { 667 // "b" is too short: there's nothing to gain 668 bigMulKV(lsA, b, c); 669 bigMulKV(msA, b, s); 670 var c1 = {v: c.v, start: c.start+half, len: c.len-half}; 671 bigAddV(c1, s, c1); 672 c.len = a.len + b.len; 673 } else { 674 var ls = {v: c.v, start: c.start}; 675 var ms = {v: c.v, start: c.start + 2*half}; 676 bigMulKV(lsA, lsB, ls); 677 bigMulKV(msA, msB, ms); 678 c.len = a.len + b.len; 679 if (c.len != ls.len + ms.len) alert("bigMulKV bad length"); 680 var midA = bigScratchV(); 681 bigAddV(lsA, msA, midA); 682 var midB; 683 if (a == b) { 684 midB = midA; 685 } else { 686 midB = bigScratchV(); 687 bigAddV(lsB, msB, midB); 688 } 689 bigMulKV(midA, midB, s); 690 if (!bigSubV(s, ls, s)) alert("bigMulKV sub ls failed"); 691 if (!bigSubV(s, ms, s)) alert("bigMulKV sub ms failed"); 692 var c1 = {v: c.v, start: c.start+half, len: c.len-half}; 693 bigAddV(c1, s, c1); 694 } 695 } 696 697 function bigMulV(a, b, m, c) { 698 // multiply sub-array "a" by "b", if "m" reduce it mod m, 699 // and place the result in "c". 700 // 701 // "m" might be an instance of "Montgomery" (see m.multiply below). 702 // 703 if (m && m.multiply) { 704 m.multiply(a, b, c); 705 } else { 706 bigMulKV(a, b, c); 707 c.len = bigLenV(c); 708 if (m) bigDivmodV(c, m, false); 709 } 710 } 711 712 713 // Power ... 714 715 function bigPowClassicV(a, b, m) { 716 // INTERNAL: for sub-arrays a, b, and optional m, compute a^b; 717 // if "m" reduce the result mod m; return the resulting sub-array. 718 // 719 // "m" might be an instance of "Montgomery" (see m.prepare below). 720 // 721 // This version uses classic square-and-multiply, l.s. digit first. 722 // 723 var temp = bigScratchV(); 724 a = {v: a.v.slice(a.start), start: 0, len: a.len}; 725 b = {v: b.v.slice(b.start), start: 0, len: b.len}; 726 var c = bigScratchV(); 727 c.len = 1; 728 c.v[c.start] = 1; 729 if (m && m.prepare) c = m.prepare(c); 730 while (true) { 731 var rem = bigDivIntV(b, 2, b); 732 if (rem > 0) { 733 bigMulV(c, a, m, temp); 734 var foo = c; c = temp; temp = foo; 735 } 736 // Invariant: at this point, b.len > 0 (proof by induction) 737 if (b.v[b.start + b.len - 1] === 0) b.len--; 738 if (b.len === 0) break; 739 bigMulV(a, a, m, temp); 740 var foo = a; a = temp; temp = foo; 741 } 742 return c; 743 } 744 745 function bigPowSlidingV(a, b, m) { 746 // INTERNAL: for sub-arrays a, b, and optional m, compute a^b; 747 // if "m" reduce the result mod m; return the resulting sub-array. 748 // 749 // "m" might be an instance of "Montgomery" (see m.prepare below). 750 // 751 // This version is sliding-window exponentation, algorithm 14.85 in 752 // the Handbook of Applied Cryptography. 753 // 754 // It relies on "radix" being a power of 2 (JavaScript bit-shift 755 // operators work on only 32 bits). 756 // 757 var k = 7; // chosen by experiment; must be <= 32 - radixBits + 1; 758 var pre = []; // pre-computed odd powers of "a" 759 pre[1] = a; 760 var temp = bigScratchV(); 761 bigMulV(a, a, m, temp); 762 for (var i = 3; i < (1<<k); i+=2) { 763 var p = bigScratchV(); 764 bigMulV(pre[i-2], temp, m, p); 765 pre[i] = p; 766 } 767 var c = bigScratchV(); 768 c.len = 1; 769 c.v[c.start] = 1; 770 if (m && m.prepare) c = m.prepare(c); 771 var digit = 0; 772 var digitBits = 0; 773 for (var nt = b.len-1; nt >= 0; nt--) { 774 digit = b.v[b.start + nt] + (digit << radixBits); 775 digitBits += radixBits; 776 while (digitBits >= k || (nt === 0 && digitBits > 0)) { 777 if (digit >>> (digitBits - 1) === 0) { 778 bigMulV(c, c, m, temp); 779 var foo = c; c = temp; temp = foo; 780 digitBits--; 781 } else { 782 var n = k; 783 if (n > digitBits) n = digitBits; 784 while (n > 1 && 785 (digit & (1 << (digitBits - n))) === 0) n--; 786 for (var i = 0; i < n; i++) { 787 bigMulV(c, c, m, temp); 788 var foo = c; c = temp; temp = foo; 789 } 790 var bBits = digit >>> (digitBits - n); // always odd 791 bigMulV(c, pre[bBits], m, temp); 792 var foo = c; c = temp; temp = foo; 793 digit -= bBits << (digitBits - n); 794 digitBits -= n; 795 } 796 } 797 } 798 return c; 799 } 800 801 function verify3(a, b, m, c) { 802 // Verify bigPowV by using bigPowClassicV 803 // 804 var t = bigPowClassicV(a, b, m); 805 if (bigCompareV(t, c) !== 0) { 806 for (var i = c.len-1; i >= 0; i--) 807 if (t.v[t.start+1] != c.v[c.start+i]) break; 808 alert("Bug in bigPowV: c.len=" + c.len + " t.len=" + t.len + 809 " m.len=" + m.len + 810 " at i=" + i + 811 " c.v = " + c.v[c.start+i].toString(16) + 812 " t.v = " + t.v[t.start+i].toString(16)); 813 } 814 return t; 815 } 816 817 function bigPowV(a, b, m) { 818 // for sub-arrays a, b, and optional m, compute a^b; 819 // if "m" reduce the result mod m; return the resulting sub-array. 820 // 821 // This version is a wrapper that uses Montgomery when appropriate 822 // 823 if (m && m.v && m.v[0] % 2 == 1 && false) { // coprime with radix 824 var montgomery = new Montgomery(m); 825 var ar = montgomery.prepare(a); 826 var cr = bigPowSlidingV(ar, b, montgomery); 827 var c = bigScratchV(); 828 montgomery.reduce(cr, c); 829 return c; 830 } else { 831 c = bigPowSlidingV(a, b, m); 832 } 833 if (verify) c = verify3(a, b, m, c); 834 return c; 835 } 836 837 Bigint.subArray = { 838 scratch: bigScratchV, 839 len: bigLenV, 840 toBig: bigFromV, 841 compare: bigCompareV, 842 add: bigAddV, 843 sub: bigSubV, 844 divInt: bigDivIntV, 845 divmod: bigDivmodV, 846 mulInt: bigMulIntV, 847 mul: bigMulV, 848 pow: bigPowV, 849 Montgomery: Montgomery 850 } 851 852 853 // 854 // The Bigint basic arithmetic methods 855 // 856 857 Bigint.zero = new Bigint(0); 858 Bigint.one = new Bigint(1); 859 Bigint.two = new Bigint(2); 860 861 Bigint.prototype.toString = function bigToString(hex) { 862 // Convert "this" to a string of decimal digits, or NaN. 863 // 864 // Output is hex iff "hex", and otherwise decimal. 865 // 866 if (this.NaN) { 867 return "NaN" + (typeof(this.NaN) == "string" ? 868 " (" + this.NaN + ")" : ""); 869 } 870 var clump = (hex ? 16 * 1024 * 1024 : 10 * 1000 * 1000); 871 var digits = (hex ? 6 : 7); 872 var t = this.toV(true); 873 var res = []; 874 while (t.len > 0) { 875 if (t.v[t.start + t.len - 1] === 0) { 876 t.len--; 877 } else { 878 res.push(bigDivIntV(t, clump, t)); 879 } 880 } 881 if (res.length === 0) return "0"; 882 var s = ""; 883 for (var i = 0; i < res.length; i++) { 884 // "res" has l.s. digits first 885 var d = res[i].toString(hex ? 16 : 10); 886 if (i < res.length-1) { 887 // insert leading zeros, except at the very front 888 var dLen = d.length; 889 for (var j = 0; j < digits - dLen; j++) d = "0" + d; 890 } 891 s = d + s; 892 } 893 if (this.neg) s = "-" + s; 894 return s; 895 }; 896 897 Bigint.prototype.absComp = function bigAbsComp(b) { 898 // Return (-1, 0, +1) if |this| is (<, =, >) |b| 899 // 900 if (this.NaN || b.NaN) return Number("a"); // NaN; 901 return bigCompareV(this.toV(), b.toV()); 902 }; 903 904 Bigint.prototype.compare = function bigCompare(b) { 905 // Return (-1, 0, +1) if this is (<, =, >) b 906 // 907 if (this.neg == b.neg) { 908 return (this.neg ? -this.absComp(b) : this.absComp(b)); 909 } else { 910 if (this.NaN || b.NaN) return Number("a"); // NaN 911 return (this.neg ? -1 : 1); 912 } 913 }; 914 915 Bigint.prototype.negate = function bigNegate() { 916 // Return negative "this" 917 // 918 if (this.NaN) return this; 919 if (this.v.length == 1 && this.v[0] === 0) return this; 920 var res = new Bigint(); 921 res.v = this.v; 922 res.neg = !this.neg; 923 res.NaN = false; 924 return res; 925 }; 926 927 Bigint.prototype.add = function bigAdd(b) { 928 // Return "this + b" 929 // 930 if (this.NaN) return this; 931 if (b.NaN) return b; 932 if (this.neg != b.neg) return this.sub(b.negate()); 933 var aSub = this.toV(); 934 var bSub = b.toV(); 935 var cSub = bigScratchV(); 936 bigAddV(aSub, bSub, cSub); 937 return bigFromV(cSub, this.neg); 938 }; 939 940 Bigint.prototype.sub = function bigSub(b) { 941 // Return "this - b" 942 // 943 if (this.NaN) return this; 944 if (b.NaN) return b; 945 if (b.v.length == 1 && b.v[0] === 0) return this; 946 if (this.neg != b.neg) return this.add(b.negate()); 947 var aSub = this.toV(); 948 var bSub = b.toV(); 949 var cSub = bigScratchV(); 950 var ok = bigSubV(aSub, bSub, cSub); 951 if (!ok) return b.sub(this).negate(); // |b| > |a| 952 return bigFromV(cSub, this.neg); 953 }; 954 955 Bigint.prototype.divmod = function bigDivmod(b, mod) { 956 // Return "this / b" or "this mod b", depending on boolean "mod". 957 // 958 // "this / b" is rounded towards zero. 959 // 960 // "this mod b" equals "this - (this / b) * b", and so is negative 961 // when "this / b" is negative. This behavior matches EcmaScript 962 // "Number" behavior. It can be adjusted easily by adding "m" back 963 // in. 964 // 965 if (this.NaN) return this; 966 if (b.NaN) return b; 967 if (b.absComp(Bigint.zero) === 0) { 968 return new Bigint("divide by zero"); 969 } 970 var aSub = this.toV(true); // will be overwritten with remainder 971 var bSub = b.toV(); 972 var q = (mod ? false : bigScratchV()); 973 bigDivmodV(aSub, bSub, q); 974 return bigFromV((mod ? aSub : q), (this.neg != b.neg)); 975 }; 976 977 Bigint.prototype.div = function bigDiv(b) { 978 // Return "this / b" 979 // 980 return this.divmod(b, false); 981 }; 982 983 Bigint.prototype.mod = function bigMod(b) { 984 // Return "this mod b" 985 // 986 return this.divmod(b, true); 987 }; 988 989 Bigint.prototype.mul = function bigMul(b, m) { 990 // Return "this * b" or "(this * b) mod m" depending on m. 991 // 992 if (this.NaN) return this; 993 if (b.NaN) return b; 994 if (m && m.NaN) return m; 995 var aSub = this.toV(); 996 var bSub = (this == b ? aSub : b.toV()); 997 var mSub = (m ? m.toV() : false); 998 var cSub = bigScratchV(); 999 bigMulV(aSub, bSub, mSub, cSub); 1000 return bigFromV(cSub, (this.neg != b.neg)); 1001 }; 1002 1003 Bigint.prototype.mulInt = function bigMulInt(k) { 1004 // Return "this * k", for normal integer "k". 1005 // 1006 // Entirely equivalent to this.mul(new Bigint(k)), but faster 1007 // 1008 if (this.NaN) return this; 1009 if (k > radix) { 1010 return this.mul(new Bigint(k)); 1011 } else if (k < 0) { 1012 return this.mulInt(-k).negate(); 1013 } else if (k === 0) { 1014 return Bigint.zero; 1015 } else if (k == 1) { 1016 return this; 1017 } else { 1018 var c = bigScratchV(); 1019 bigMulIntV(this.toV(), k, c); 1020 return bigFromV(c, this.neg); 1021 } 1022 }; 1023 1024 Bigint.prototype.pow = function bigPow(b, m) { 1025 // Return "this ^ b" or "(this ^ b) mod m" depending on m. 1026 // Note that, following EcmaScript, NaN.pow(0) == 1. 1027 // 1028 if (b.NaN) return b; 1029 if (b.neg) return new Bigint("negative exponent"); 1030 if (this.NaN) { 1031 return (b.absComp(Bigint.zero) === 0 ? Bigint.one : this); 1032 } 1033 if (m && m.NaN) return m; 1034 if (m && m.absComp(Bigint.zero) === 0) return new Bigint( 1035 "divide by zero"); 1036 var aSub = this.toV(); 1037 var bSub = b.toV(); 1038 var mSub = (m ? m.toV() : false); 1039 if (!m && (bSub.len > 1 || 1040 aSub.len * radixBits * bSub.v[0] > 99999999)) { 1041 return new Bigint("infeasible, too large"); 1042 } 1043 var cSub = bigPowV(aSub, bSub, mSub); 1044 return bigFromV(cSub, this.neg && (b.v[0] % 2) !== 0); 1045 }; 1046 1047 1048 // 1049 // Some number theory methods 1050 // 1051 1052 Bigint.prototype.gcd = function bigGCD(b) { 1053 // Return GCD(this, b). 1054 // 1055 // Euclid's algorithm. The binary algorithm is probably faster. 1056 // 1057 if (this.NaN) return this; 1058 if (b.NaN) return b; 1059 if (this.neg) return this.negate().gcd(b); 1060 if (b.neg) return this.gcd(b.negate()); 1061 var big = (this.absComp(b) > 0 ? this : b); 1062 var small = (big == this ? b : this); 1063 while (small.absComp(Bigint.zero) !== 0) { 1064 var rem = big.mod(small); 1065 big = small; 1066 small = rem; 1067 } 1068 return big; 1069 }; 1070 1071 Bigint.prototype.inverse = function bigInverse(b) { 1072 // Return "c" s.t. "(this * c) mod b == 1". 1073 // 1074 // A special case of the extended Euclidean algorithm. 1075 // Returns NaN if GCD(this, b) != 1. 1076 // 1077 if (this.NaN) return this; 1078 if (b.NaN) return b; 1079 if (this.neg || b.neg) 1080 return new Bigint("modular inverse of negative number"); 1081 var x = Bigint.one; 1082 var lastX = Bigint.zero; 1083 var big = b; 1084 var small = (this.absComp(b) < 0 ? this : this.mod(b)); 1085 while (small.absComp(Bigint.zero) !== 0) { 1086 var quotient = big.div(small); 1087 var rem = big.mod(small); 1088 big = small; 1089 small = rem; 1090 var t = x; 1091 x = lastX.sub(quotient.mul(x)); 1092 lastX = t; 1093 } 1094 if (big.absComp(Bigint.one) !== 0) 1095 return new Bigint("modular inverse with GCD not 1"); 1096 if (lastX.neg) lastX = lastX.add(b); 1097 return lastX; 1098 }; 1099 1100 Bigint.randomInt = function(n) { 1101 // Return a random integer i such that 0 <= i < n 1102 // 1103 // "Math.random" is not an adequate source of cryptographically 1104 // random values. Anyone who cares should replace this method. 1105 // 1106 var res; 1107 while ((res = Math.floor(Math.random() * n)) >= n) {}; 1108 // The loop is for the very unlikely case where the multiplication 1109 // rounded up to equal "n". 1110 return res; 1111 } 1112 1113 Bigint.prototype.randomLT = function bigRandomLT() { 1114 // Returns a fairly random positive Bigint less than |this| 1115 // 1116 if (this.absComp(Bigint.zero) === 0) return new Bigint( 1117 "random with 0 bits"); 1118 var res = new Bigint(0); 1119 var max = this.sub(Bigint.one); 1120 var lt = false; // true iff some more significant digit is < max 1121 for (var i = max.v.length-1; i >= 0; i--) { 1122 var digit; 1123 if (lt) { 1124 digit = Bigint.randomInt(radix); 1125 } else { 1126 digit = Bigint.randomInt(max.v[i] + 1); 1127 if (digit < max.v[i]) lt = true; 1128 } 1129 res.v[i] = digit; 1130 } 1131 res.normalize(); 1132 return res; 1133 }; 1134 1135 Bigint.prototype.rabin = function bigRabin(nMinus1, s, d, a) { 1136 // Inner loop of Miller-Rabin primality test. 1137 // Return true if "this" appears to be prime. 1138 // 1139 // First, for convenience, ignore a <= 1 and a >= n-1 1140 if (a.absComp(Bigint.one) <= 0 || 1141 a.absComp(nMinus1) >= 0) return true; 1142 var p = a.pow(d, this); 1143 if (p.absComp(Bigint.one) === 0) return true; 1144 if (p.absComp(nMinus1) === 0) return true; 1145 for (var i = 0; i < s-1; i++) { 1146 p = p.mul(p, this); 1147 if (p.absComp(Bigint.one) === 0) return false; 1148 if (p.absComp(nMinus1) === 0) return true; 1149 } 1150 return false; 1151 }; 1152 1153 var jaeschke = new Bigint("3825123056546413051"); 1154 // Miller-Rabin is deterministic using first 9 primes below this 1155 // http://oeis.org/A014233 1156 // G. Jaeschke, Mathematics of Computation, 61 (1993), 915-926 1157 var jaeschkeN = 9; 1158 1159 var smallPrimes = null; // A cache, filled in "isPrime" 1160 var jPrimes = null; // Bigint primes, for the Jaeschke test 1161 1162 function eratosthenes(n) { 1163 // Return an array containing the primes less than n 1164 // 1165 // The sieve of Eratosthenes 1166 // 1167 var res = []; 1168 var sieve = []; 1169 var p = 2; 1170 while (p * p < n) { 1171 res[res.length] = p; 1172 for (var multiple = p; multiple < n; multiple += p) { 1173 sieve[multiple] = true; 1174 } 1175 while (sieve[p]) p++; 1176 } 1177 for (; p < n; p++) if (!sieve[p]) res[res.length] = p; 1178 return res; 1179 } 1180 1181 Bigint.prototype.isPrime = function bigIsPrime() { 1182 // Return true iff "this" is probably prime, as indicated by running 1183 // the Miller-Rabin probabalistic primality test such that the 1184 // probability of a false positive is < 1:2^80. 1185 // 1186 // For numbers < "jaeschke", result is correct, not probabilistic. 1187 // 1188 if (this.NaN || this.neg) return false; 1189 var thisInt = (this.v.length > 1 ? radix * radix : this.v[0]); 1190 if (thisInt <= 1) return false; 1191 1192 if (!smallPrimes) { 1193 smallPrimes = eratosthenes(100 * 1000); 1194 jPrimes = []; 1195 for (var p = 0; p < jaeschkeN; p++) { 1196 jPrimes[p] = new Bigint(smallPrimes[p]); 1197 } 1198 } 1199 var thisSub = this.toV(); 1200 for (var p = 0; p < smallPrimes.length; p++) { 1201 var smallP = smallPrimes[p]; 1202 if (smallP >= radix) break; 1203 if (thisInt < smallP * smallP) return true; 1204 if (bigDivIntV(thisSub, smallP, false) === 0) return false; 1205 } 1206 1207 // First, setup n-1, s and d, s.t. d is odd and d*2^s = n-1 1208 var nMinus1 = this.sub(Bigint.one); 1209 var s = 0; 1210 var t = nMinus1.toV(true); 1211 while (true) { // note that nMinus1 > 0, so we always terminate. 1212 if (t.v[t.start + t.len - 1] === 0) { 1213 t.len--; 1214 } else if (bigDivIntV(t, 2, t) > 0) { 1215 break; 1216 } else { 1217 s++; 1218 } 1219 } 1220 var d = bigFromV(t, false); 1221 // But we really want d = d*2+1 1222 d = d.mulInt(2).add(Bigint.one); 1223 // Done creating nMinus1, s, and d 1224 1225 if (this.absComp(jaeschke) < 0) { 1226 for (var p = 0; p < jaeschkeN; p++) { 1227 if (!this.rabin(nMinus1, s, d, jPrimes[p])) return false; 1228 } 1229 } else { 1230 var thisBits = (this.v.length - 1) * radixBits; // lower bound 1231 // We choose "trials" to achieve an error probability 1 in 2^80, 1232 // using tables 4.3 and 4.4 of Handbook of Applied Cryptography. 1233 var trials = ( // first, ones from table 4.3 1234 thisBits >= 600 ? 2 : 1235 thisBits >= 550 ? 4 : 1236 thisBits >= 500 ? 5 : 1237 thisBits >= 400 ? 6 : 1238 thisBits >= 350 ? 7 : 1239 thisBits >= 300 ? 9 : 1240 // then, ones from table 4.4 1241 thisBits >= 250 ? 12 : 1242 thisBits >= 200 ? 15 : 1243 thisBits >= 150 ? 18 : 1244 thisBits >= 100 ? 27 : 1245 // finally, the basic (1/4)^t 1246 40); 1247 for (var i = 0; i < trials; i++) { 1248 var a = nMinus1.randomLT(); 1249 if (!this.rabin(nMinus1, s, d, a)) return false; 1250 if (a.absComp(Bigint.one) <= 0) i--; // it didn't count 1251 } 1252 } 1253 return true; 1254 }; 1255 1256 Bigint.random = function (bits) { 1257 // Returns a random Bigint uniformly distributed in 1258 // [0..2^bits-1]. 1259 // 1260 if (!bits || bits <= 0) return new Bigint("random with 0 bits"); 1261 return Bigint.two.pow(new Bigint(bits)).randomLT(); 1262 }; 1263 1264 Bigint.prime = function (bits) { 1265 // Returns a random probable prime uniformly distributed in 1266 // [2^(bits-1)..2^bits-1] 1267 // 1268 // Note that, unlike "Bigint.random", the top bit is always 1. 1269 // 1270 // We previously limited the search to 5000 iterations; the current 1271 // version limits it to 20 seconds. 1272 // 1273 var d = new Date(); 1274 var limit = d.getTime() + 20 * 1000; 1275 if (!bits || bits <= 0) return new Bigint("prime with 0 bits"); 1276 var top = Bigint.two.pow(new Bigint(bits-1)); 1277 while (true) { 1278 var r = top.randomLT().add(top); 1279 if (r.isPrime()) return r; 1280 var d2 = new Date(); 1281 if (d2.getTime() > limit) return new Bigint( 1282 "no prime found in 20 seconds") 1283 } 1284 }; 1285 1286 1287 return Bigint; 1288 })(); // End of the class creation
End of listing