1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
10 |
|
11 |
|
12 |
|
13 |
|
14 |
|
15 |
|
16 |
|
17 |
|
18 | export default BigInteger;
|
19 |
|
20 |
|
21 |
|
22 |
|
23 |
|
24 |
|
25 |
|
26 |
|
27 |
|
28 |
|
29 |
|
30 |
|
31 |
|
32 |
|
33 |
|
34 |
|
35 |
|
36 |
|
37 |
|
38 |
|
39 |
|
40 |
|
41 |
|
42 |
|
43 |
|
44 |
|
45 |
|
46 |
|
47 |
|
48 |
|
49 |
|
50 |
|
51 |
|
52 | function BigInteger(a, b) {
|
53 | if (a != null) this.fromString(a, b);
|
54 | }
|
55 |
|
56 |
|
57 | function nbi() {
|
58 | return new BigInteger(null);
|
59 | }
|
60 |
|
61 |
|
62 | var dbits;
|
63 |
|
64 |
|
65 | var canary = 0xdeadbeefcafe;
|
66 | var j_lm = (canary & 0xffffff) == 0xefcafe;
|
67 |
|
68 |
|
69 |
|
70 |
|
71 |
|
72 |
|
73 |
|
74 |
|
75 |
|
76 | function am1(i, x, w, j, c, n) {
|
77 | while (--n >= 0) {
|
78 | var v = x * this[i++] + w[j] + c;
|
79 | c = Math.floor(v / 0x4000000);
|
80 | w[j++] = v & 0x3ffffff;
|
81 | }
|
82 | return c;
|
83 | }
|
84 |
|
85 |
|
86 |
|
87 | function am2(i, x, w, j, c, n) {
|
88 | var xl = x & 0x7fff,
|
89 | xh = x >> 15;
|
90 | while (--n >= 0) {
|
91 | var l = this[i] & 0x7fff;
|
92 | var h = this[i++] >> 15;
|
93 | var m = xh * l + h * xl;
|
94 | l = xl * l + ((m & 0x7fff) << 15) + w[j] + (c & 0x3fffffff);
|
95 | c = (l >>> 30) + (m >>> 15) + xh * h + (c >>> 30);
|
96 | w[j++] = l & 0x3fffffff;
|
97 | }
|
98 | return c;
|
99 | }
|
100 |
|
101 |
|
102 | function am3(i, x, w, j, c, n) {
|
103 | var xl = x & 0x3fff,
|
104 | xh = x >> 14;
|
105 | while (--n >= 0) {
|
106 | var l = this[i] & 0x3fff;
|
107 | var h = this[i++] >> 14;
|
108 | var m = xh * l + h * xl;
|
109 | l = xl * l + ((m & 0x3fff) << 14) + w[j] + c;
|
110 | c = (l >> 28) + (m >> 14) + xh * h;
|
111 | w[j++] = l & 0xfffffff;
|
112 | }
|
113 | return c;
|
114 | }
|
115 | var inBrowser = typeof navigator !== 'undefined';
|
116 | if (inBrowser && j_lm && navigator.appName == 'Microsoft Internet Explorer') {
|
117 | BigInteger.prototype.am = am2;
|
118 | dbits = 30;
|
119 | } else if (inBrowser && j_lm && navigator.appName != 'Netscape') {
|
120 | BigInteger.prototype.am = am1;
|
121 | dbits = 26;
|
122 | } else {
|
123 |
|
124 | BigInteger.prototype.am = am3;
|
125 | dbits = 28;
|
126 | }
|
127 |
|
128 | BigInteger.prototype.DB = dbits;
|
129 | BigInteger.prototype.DM = (1 << dbits) - 1;
|
130 | BigInteger.prototype.DV = 1 << dbits;
|
131 |
|
132 | var BI_FP = 52;
|
133 | BigInteger.prototype.FV = Math.pow(2, BI_FP);
|
134 | BigInteger.prototype.F1 = BI_FP - dbits;
|
135 | BigInteger.prototype.F2 = 2 * dbits - BI_FP;
|
136 |
|
137 |
|
138 | var BI_RM = '0123456789abcdefghijklmnopqrstuvwxyz';
|
139 | var BI_RC = new Array();
|
140 | var rr, vv;
|
141 | rr = '0'.charCodeAt(0);
|
142 | for (vv = 0; vv <= 9; ++vv) BI_RC[rr++] = vv;
|
143 | rr = 'a'.charCodeAt(0);
|
144 | for (vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv;
|
145 | rr = 'A'.charCodeAt(0);
|
146 | for (vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv;
|
147 |
|
148 | function int2char(n) {
|
149 | return BI_RM.charAt(n);
|
150 | }
|
151 | function intAt(s, i) {
|
152 | var c = BI_RC[s.charCodeAt(i)];
|
153 | return c == null ? -1 : c;
|
154 | }
|
155 |
|
156 |
|
157 | function bnpCopyTo(r) {
|
158 | for (var i = this.t - 1; i >= 0; --i) r[i] = this[i];
|
159 | r.t = this.t;
|
160 | r.s = this.s;
|
161 | }
|
162 |
|
163 |
|
164 | function bnpFromInt(x) {
|
165 | this.t = 1;
|
166 | this.s = x < 0 ? -1 : 0;
|
167 | if (x > 0) this[0] = x;
|
168 | else if (x < -1) this[0] = x + this.DV;
|
169 | else this.t = 0;
|
170 | }
|
171 |
|
172 |
|
173 | function nbv(i) {
|
174 | var r = nbi();
|
175 |
|
176 | r.fromInt(i);
|
177 |
|
178 | return r;
|
179 | }
|
180 |
|
181 |
|
182 | function bnpFromString(s, b) {
|
183 | var k;
|
184 | if (b == 16) k = 4;
|
185 | else if (b == 8) k = 3;
|
186 | else if (b == 2) k = 1;
|
187 | else if (b == 32) k = 5;
|
188 | else if (b == 4) k = 2;
|
189 | else throw new Error('Only radix 2, 4, 8, 16, 32 are supported');
|
190 | this.t = 0;
|
191 | this.s = 0;
|
192 | var i = s.length,
|
193 | mi = false,
|
194 | sh = 0;
|
195 | while (--i >= 0) {
|
196 | var x = intAt(s, i);
|
197 | if (x < 0) {
|
198 | if (s.charAt(i) == '-') mi = true;
|
199 | continue;
|
200 | }
|
201 | mi = false;
|
202 | if (sh == 0) this[this.t++] = x;
|
203 | else if (sh + k > this.DB) {
|
204 | this[this.t - 1] |= (x & ((1 << (this.DB - sh)) - 1)) << sh;
|
205 | this[this.t++] = x >> (this.DB - sh);
|
206 | } else this[this.t - 1] |= x << sh;
|
207 | sh += k;
|
208 | if (sh >= this.DB) sh -= this.DB;
|
209 | }
|
210 | this.clamp();
|
211 | if (mi) BigInteger.ZERO.subTo(this, this);
|
212 | }
|
213 |
|
214 |
|
215 | function bnpClamp() {
|
216 | var c = this.s & this.DM;
|
217 | while (this.t > 0 && this[this.t - 1] == c) --this.t;
|
218 | }
|
219 |
|
220 |
|
221 | function bnToString(b) {
|
222 | if (this.s < 0) return '-' + this.negate().toString(b);
|
223 | var k;
|
224 | if (b == 16) k = 4;
|
225 | else if (b == 8) k = 3;
|
226 | else if (b == 2) k = 1;
|
227 | else if (b == 32) k = 5;
|
228 | else if (b == 4) k = 2;
|
229 | else throw new Error('Only radix 2, 4, 8, 16, 32 are supported');
|
230 | var km = (1 << k) - 1,
|
231 | d,
|
232 | m = false,
|
233 | r = '',
|
234 | i = this.t;
|
235 | var p = this.DB - ((i * this.DB) % k);
|
236 | if (i-- > 0) {
|
237 | if (p < this.DB && (d = this[i] >> p) > 0) {
|
238 | m = true;
|
239 | r = int2char(d);
|
240 | }
|
241 | while (i >= 0) {
|
242 | if (p < k) {
|
243 | d = (this[i] & ((1 << p) - 1)) << (k - p);
|
244 | d |= this[--i] >> (p += this.DB - k);
|
245 | } else {
|
246 | d = (this[i] >> (p -= k)) & km;
|
247 | if (p <= 0) {
|
248 | p += this.DB;
|
249 | --i;
|
250 | }
|
251 | }
|
252 | if (d > 0) m = true;
|
253 | if (m) r += int2char(d);
|
254 | }
|
255 | }
|
256 | return m ? r : '0';
|
257 | }
|
258 |
|
259 |
|
260 | function bnNegate() {
|
261 | var r = nbi();
|
262 |
|
263 | BigInteger.ZERO.subTo(this, r);
|
264 |
|
265 | return r;
|
266 | }
|
267 |
|
268 |
|
269 | function bnAbs() {
|
270 | return this.s < 0 ? this.negate() : this;
|
271 | }
|
272 |
|
273 |
|
274 | function bnCompareTo(a) {
|
275 | var r = this.s - a.s;
|
276 | if (r != 0) return r;
|
277 | var i = this.t;
|
278 | r = i - a.t;
|
279 | if (r != 0) return this.s < 0 ? -r : r;
|
280 | while (--i >= 0) if ((r = this[i] - a[i]) != 0) return r;
|
281 | return 0;
|
282 | }
|
283 |
|
284 |
|
285 | function nbits(x) {
|
286 | var r = 1,
|
287 | t;
|
288 | if ((t = x >>> 16) != 0) {
|
289 | x = t;
|
290 | r += 16;
|
291 | }
|
292 | if ((t = x >> 8) != 0) {
|
293 | x = t;
|
294 | r += 8;
|
295 | }
|
296 | if ((t = x >> 4) != 0) {
|
297 | x = t;
|
298 | r += 4;
|
299 | }
|
300 | if ((t = x >> 2) != 0) {
|
301 | x = t;
|
302 | r += 2;
|
303 | }
|
304 | if ((t = x >> 1) != 0) {
|
305 | x = t;
|
306 | r += 1;
|
307 | }
|
308 | return r;
|
309 | }
|
310 |
|
311 |
|
312 | function bnBitLength() {
|
313 | if (this.t <= 0) return 0;
|
314 | return this.DB * (this.t - 1) + nbits(this[this.t - 1] ^ (this.s & this.DM));
|
315 | }
|
316 |
|
317 |
|
318 | function bnpDLShiftTo(n, r) {
|
319 | var i;
|
320 | for (i = this.t - 1; i >= 0; --i) r[i + n] = this[i];
|
321 | for (i = n - 1; i >= 0; --i) r[i] = 0;
|
322 | r.t = this.t + n;
|
323 | r.s = this.s;
|
324 | }
|
325 |
|
326 |
|
327 | function bnpDRShiftTo(n, r) {
|
328 | for (var i = n; i < this.t; ++i) r[i - n] = this[i];
|
329 | r.t = Math.max(this.t - n, 0);
|
330 | r.s = this.s;
|
331 | }
|
332 |
|
333 |
|
334 | function bnpLShiftTo(n, r) {
|
335 | var bs = n % this.DB;
|
336 | var cbs = this.DB - bs;
|
337 | var bm = (1 << cbs) - 1;
|
338 | var ds = Math.floor(n / this.DB),
|
339 | c = (this.s << bs) & this.DM,
|
340 | i;
|
341 | for (i = this.t - 1; i >= 0; --i) {
|
342 | r[i + ds + 1] = (this[i] >> cbs) | c;
|
343 | c = (this[i] & bm) << bs;
|
344 | }
|
345 | for (i = ds - 1; i >= 0; --i) r[i] = 0;
|
346 | r[ds] = c;
|
347 | r.t = this.t + ds + 1;
|
348 | r.s = this.s;
|
349 | r.clamp();
|
350 | }
|
351 |
|
352 |
|
353 | function bnpRShiftTo(n, r) {
|
354 | r.s = this.s;
|
355 | var ds = Math.floor(n / this.DB);
|
356 | if (ds >= this.t) {
|
357 | r.t = 0;
|
358 | return;
|
359 | }
|
360 | var bs = n % this.DB;
|
361 | var cbs = this.DB - bs;
|
362 | var bm = (1 << bs) - 1;
|
363 | r[0] = this[ds] >> bs;
|
364 | for (var i = ds + 1; i < this.t; ++i) {
|
365 | r[i - ds - 1] |= (this[i] & bm) << cbs;
|
366 | r[i - ds] = this[i] >> bs;
|
367 | }
|
368 | if (bs > 0) r[this.t - ds - 1] |= (this.s & bm) << cbs;
|
369 | r.t = this.t - ds;
|
370 | r.clamp();
|
371 | }
|
372 |
|
373 |
|
374 | function bnpSubTo(a, r) {
|
375 | var i = 0,
|
376 | c = 0,
|
377 | m = Math.min(a.t, this.t);
|
378 | while (i < m) {
|
379 | c += this[i] - a[i];
|
380 | r[i++] = c & this.DM;
|
381 | c >>= this.DB;
|
382 | }
|
383 | if (a.t < this.t) {
|
384 | c -= a.s;
|
385 | while (i < this.t) {
|
386 | c += this[i];
|
387 | r[i++] = c & this.DM;
|
388 | c >>= this.DB;
|
389 | }
|
390 | c += this.s;
|
391 | } else {
|
392 | c += this.s;
|
393 | while (i < a.t) {
|
394 | c -= a[i];
|
395 | r[i++] = c & this.DM;
|
396 | c >>= this.DB;
|
397 | }
|
398 | c -= a.s;
|
399 | }
|
400 | r.s = c < 0 ? -1 : 0;
|
401 | if (c < -1) r[i++] = this.DV + c;
|
402 | else if (c > 0) r[i++] = c;
|
403 | r.t = i;
|
404 | r.clamp();
|
405 | }
|
406 |
|
407 |
|
408 |
|
409 | function bnpMultiplyTo(a, r) {
|
410 | var x = this.abs(),
|
411 | y = a.abs();
|
412 | var i = x.t;
|
413 | r.t = i + y.t;
|
414 | while (--i >= 0) r[i] = 0;
|
415 | for (i = 0; i < y.t; ++i) r[i + x.t] = x.am(0, y[i], r, i, 0, x.t);
|
416 | r.s = 0;
|
417 | r.clamp();
|
418 | if (this.s != a.s) BigInteger.ZERO.subTo(r, r);
|
419 | }
|
420 |
|
421 |
|
422 | function bnpSquareTo(r) {
|
423 | var x = this.abs();
|
424 | var i = (r.t = 2 * x.t);
|
425 | while (--i >= 0) r[i] = 0;
|
426 | for (i = 0; i < x.t - 1; ++i) {
|
427 | var c = x.am(i, x[i], r, 2 * i, 0, 1);
|
428 | if (
|
429 | (r[i + x.t] += x.am(i + 1, 2 * x[i], r, 2 * i + 1, c, x.t - i - 1)) >=
|
430 | x.DV
|
431 | ) {
|
432 | r[i + x.t] -= x.DV;
|
433 | r[i + x.t + 1] = 1;
|
434 | }
|
435 | }
|
436 | if (r.t > 0) r[r.t - 1] += x.am(i, x[i], r, 2 * i, 0, 1);
|
437 | r.s = 0;
|
438 | r.clamp();
|
439 | }
|
440 |
|
441 |
|
442 |
|
443 | function bnpDivRemTo(m, q, r) {
|
444 | var pm = m.abs();
|
445 | if (pm.t <= 0) return;
|
446 | var pt = this.abs();
|
447 | if (pt.t < pm.t) {
|
448 | if (q != null) q.fromInt(0);
|
449 | if (r != null) this.copyTo(r);
|
450 | return;
|
451 | }
|
452 | if (r == null) r = nbi();
|
453 | var y = nbi(),
|
454 | ts = this.s,
|
455 | ms = m.s;
|
456 | var nsh = this.DB - nbits(pm[pm.t - 1]);
|
457 |
|
458 | if (nsh > 0) {
|
459 | pm.lShiftTo(nsh, y);
|
460 | pt.lShiftTo(nsh, r);
|
461 | } else {
|
462 | pm.copyTo(y);
|
463 | pt.copyTo(r);
|
464 | }
|
465 | var ys = y.t;
|
466 | var y0 = y[ys - 1];
|
467 | if (y0 == 0) return;
|
468 | var yt = y0 * (1 << this.F1) + (ys > 1 ? y[ys - 2] >> this.F2 : 0);
|
469 | var d1 = this.FV / yt,
|
470 | d2 = (1 << this.F1) / yt,
|
471 | e = 1 << this.F2;
|
472 | var i = r.t,
|
473 | j = i - ys,
|
474 | t = q == null ? nbi() : q;
|
475 | y.dlShiftTo(j, t);
|
476 | if (r.compareTo(t) >= 0) {
|
477 | r[r.t++] = 1;
|
478 | r.subTo(t, r);
|
479 | }
|
480 | BigInteger.ONE.dlShiftTo(ys, t);
|
481 | t.subTo(y, y);
|
482 |
|
483 | while (y.t < ys) y[y.t++] = 0;
|
484 | while (--j >= 0) {
|
485 |
|
486 | var qd =
|
487 | r[--i] == y0 ? this.DM : Math.floor(r[i] * d1 + (r[i - 1] + e) * d2);
|
488 | if ((r[i] += y.am(0, qd, r, j, 0, ys)) < qd) {
|
489 |
|
490 | y.dlShiftTo(j, t);
|
491 | r.subTo(t, r);
|
492 | while (r[i] < --qd) r.subTo(t, r);
|
493 | }
|
494 | }
|
495 | if (q != null) {
|
496 | r.drShiftTo(ys, q);
|
497 | if (ts != ms) BigInteger.ZERO.subTo(q, q);
|
498 | }
|
499 | r.t = ys;
|
500 | r.clamp();
|
501 | if (nsh > 0) r.rShiftTo(nsh, r);
|
502 |
|
503 | if (ts < 0) BigInteger.ZERO.subTo(r, r);
|
504 | }
|
505 |
|
506 |
|
507 | function bnMod(a) {
|
508 | var r = nbi();
|
509 | this.abs().divRemTo(a, null, r);
|
510 | if (this.s < 0 && r.compareTo(BigInteger.ZERO) > 0) a.subTo(r, r);
|
511 | return r;
|
512 | }
|
513 |
|
514 |
|
515 |
|
516 |
|
517 |
|
518 |
|
519 |
|
520 |
|
521 |
|
522 |
|
523 |
|
524 | function bnpInvDigit() {
|
525 | if (this.t < 1) return 0;
|
526 | var x = this[0];
|
527 | if ((x & 1) == 0) return 0;
|
528 | var y = x & 3;
|
529 |
|
530 | y = (y * (2 - (x & 0xf) * y)) & 0xf;
|
531 |
|
532 | y = (y * (2 - (x & 0xff) * y)) & 0xff;
|
533 |
|
534 | y = (y * (2 - (((x & 0xffff) * y) & 0xffff))) & 0xffff;
|
535 |
|
536 |
|
537 |
|
538 | y = (y * (2 - ((x * y) % this.DV))) % this.DV;
|
539 |
|
540 |
|
541 | return y > 0 ? this.DV - y : -y;
|
542 | }
|
543 |
|
544 | function bnEquals(a) {
|
545 | return this.compareTo(a) == 0;
|
546 | }
|
547 |
|
548 |
|
549 | function bnpAddTo(a, r) {
|
550 | var i = 0,
|
551 | c = 0,
|
552 | m = Math.min(a.t, this.t);
|
553 | while (i < m) {
|
554 | c += this[i] + a[i];
|
555 | r[i++] = c & this.DM;
|
556 | c >>= this.DB;
|
557 | }
|
558 | if (a.t < this.t) {
|
559 | c += a.s;
|
560 | while (i < this.t) {
|
561 | c += this[i];
|
562 | r[i++] = c & this.DM;
|
563 | c >>= this.DB;
|
564 | }
|
565 | c += this.s;
|
566 | } else {
|
567 | c += this.s;
|
568 | while (i < a.t) {
|
569 | c += a[i];
|
570 | r[i++] = c & this.DM;
|
571 | c >>= this.DB;
|
572 | }
|
573 | c += a.s;
|
574 | }
|
575 | r.s = c < 0 ? -1 : 0;
|
576 | if (c > 0) r[i++] = c;
|
577 | else if (c < -1) r[i++] = this.DV + c;
|
578 | r.t = i;
|
579 | r.clamp();
|
580 | }
|
581 |
|
582 |
|
583 | function bnAdd(a) {
|
584 | var r = nbi();
|
585 |
|
586 | this.addTo(a, r);
|
587 |
|
588 | return r;
|
589 | }
|
590 |
|
591 |
|
592 | function bnSubtract(a) {
|
593 | var r = nbi();
|
594 |
|
595 | this.subTo(a, r);
|
596 |
|
597 | return r;
|
598 | }
|
599 |
|
600 |
|
601 | function bnMultiply(a) {
|
602 | var r = nbi();
|
603 |
|
604 | this.multiplyTo(a, r);
|
605 |
|
606 | return r;
|
607 | }
|
608 |
|
609 |
|
610 | function bnDivide(a) {
|
611 | var r = nbi();
|
612 |
|
613 | this.divRemTo(a, r, null);
|
614 |
|
615 | return r;
|
616 | }
|
617 |
|
618 |
|
619 | function Montgomery(m) {
|
620 | this.m = m;
|
621 | this.mp = m.invDigit();
|
622 | this.mpl = this.mp & 0x7fff;
|
623 | this.mph = this.mp >> 15;
|
624 | this.um = (1 << (m.DB - 15)) - 1;
|
625 | this.mt2 = 2 * m.t;
|
626 | }
|
627 |
|
628 |
|
629 | function montConvert(x) {
|
630 | var r = nbi();
|
631 | x.abs().dlShiftTo(this.m.t, r);
|
632 | r.divRemTo(this.m, null, r);
|
633 | if (x.s < 0 && r.compareTo(BigInteger.ZERO) > 0) this.m.subTo(r, r);
|
634 | return r;
|
635 | }
|
636 |
|
637 |
|
638 | function montRevert(x) {
|
639 | var r = nbi();
|
640 | x.copyTo(r);
|
641 | this.reduce(r);
|
642 | return r;
|
643 | }
|
644 |
|
645 |
|
646 | function montReduce(x) {
|
647 | while (x.t <= this.mt2)
|
648 |
|
649 | x[x.t++] = 0;
|
650 | for (var i = 0; i < this.m.t; ++i) {
|
651 |
|
652 | var j = x[i] & 0x7fff;
|
653 | var u0 =
|
654 | (j * this.mpl +
|
655 | (((j * this.mph + (x[i] >> 15) * this.mpl) & this.um) << 15)) &
|
656 | x.DM;
|
657 |
|
658 | j = i + this.m.t;
|
659 | x[j] += this.m.am(0, u0, x, i, 0, this.m.t);
|
660 |
|
661 | while (x[j] >= x.DV) {
|
662 | x[j] -= x.DV;
|
663 | x[++j]++;
|
664 | }
|
665 | }
|
666 | x.clamp();
|
667 | x.drShiftTo(this.m.t, x);
|
668 | if (x.compareTo(this.m) >= 0) x.subTo(this.m, x);
|
669 | }
|
670 |
|
671 |
|
672 | function montSqrTo(x, r) {
|
673 | x.squareTo(r);
|
674 |
|
675 | this.reduce(r);
|
676 | }
|
677 |
|
678 |
|
679 | function montMulTo(x, y, r) {
|
680 | x.multiplyTo(y, r);
|
681 |
|
682 | this.reduce(r);
|
683 | }
|
684 |
|
685 | Montgomery.prototype.convert = montConvert;
|
686 | Montgomery.prototype.revert = montRevert;
|
687 | Montgomery.prototype.reduce = montReduce;
|
688 | Montgomery.prototype.mulTo = montMulTo;
|
689 | Montgomery.prototype.sqrTo = montSqrTo;
|
690 |
|
691 |
|
692 | function bnModPow(e, m, callback) {
|
693 | var i = e.bitLength(),
|
694 | k,
|
695 | r = nbv(1),
|
696 | z = new Montgomery(m);
|
697 | if (i <= 0) return r;
|
698 | else if (i < 18) k = 1;
|
699 | else if (i < 48) k = 3;
|
700 | else if (i < 144) k = 4;
|
701 | else if (i < 768) k = 5;
|
702 | else k = 6;
|
703 |
|
704 |
|
705 | var g = new Array(),
|
706 | n = 3,
|
707 | k1 = k - 1,
|
708 | km = (1 << k) - 1;
|
709 | g[1] = z.convert(this);
|
710 | if (k > 1) {
|
711 | var g2 = nbi();
|
712 | z.sqrTo(g[1], g2);
|
713 | while (n <= km) {
|
714 | g[n] = nbi();
|
715 | z.mulTo(g2, g[n - 2], g[n]);
|
716 | n += 2;
|
717 | }
|
718 | }
|
719 |
|
720 | var j = e.t - 1,
|
721 | w,
|
722 | is1 = true,
|
723 | r2 = nbi(),
|
724 | t;
|
725 | i = nbits(e[j]) - 1;
|
726 | while (j >= 0) {
|
727 | if (i >= k1) w = (e[j] >> (i - k1)) & km;
|
728 | else {
|
729 | w = (e[j] & ((1 << (i + 1)) - 1)) << (k1 - i);
|
730 | if (j > 0) w |= e[j - 1] >> (this.DB + i - k1);
|
731 | }
|
732 |
|
733 | n = k;
|
734 | while ((w & 1) == 0) {
|
735 | w >>= 1;
|
736 | --n;
|
737 | }
|
738 | if ((i -= n) < 0) {
|
739 | i += this.DB;
|
740 | --j;
|
741 | }
|
742 | if (is1) {
|
743 |
|
744 | g[w].copyTo(r);
|
745 | is1 = false;
|
746 | } else {
|
747 | while (n > 1) {
|
748 | z.sqrTo(r, r2);
|
749 | z.sqrTo(r2, r);
|
750 | n -= 2;
|
751 | }
|
752 | if (n > 0) z.sqrTo(r, r2);
|
753 | else {
|
754 | t = r;
|
755 | r = r2;
|
756 | r2 = t;
|
757 | }
|
758 | z.mulTo(r2, g[w], r);
|
759 | }
|
760 |
|
761 | while (j >= 0 && (e[j] & (1 << i)) == 0) {
|
762 | z.sqrTo(r, r2);
|
763 | t = r;
|
764 | r = r2;
|
765 | r2 = t;
|
766 | if (--i < 0) {
|
767 | i = this.DB - 1;
|
768 | --j;
|
769 | }
|
770 | }
|
771 | }
|
772 | var result = z.revert(r);
|
773 | callback(null, result);
|
774 | return result;
|
775 | }
|
776 |
|
777 |
|
778 | BigInteger.prototype.copyTo = bnpCopyTo;
|
779 | BigInteger.prototype.fromInt = bnpFromInt;
|
780 | BigInteger.prototype.fromString = bnpFromString;
|
781 | BigInteger.prototype.clamp = bnpClamp;
|
782 | BigInteger.prototype.dlShiftTo = bnpDLShiftTo;
|
783 | BigInteger.prototype.drShiftTo = bnpDRShiftTo;
|
784 | BigInteger.prototype.lShiftTo = bnpLShiftTo;
|
785 | BigInteger.prototype.rShiftTo = bnpRShiftTo;
|
786 | BigInteger.prototype.subTo = bnpSubTo;
|
787 | BigInteger.prototype.multiplyTo = bnpMultiplyTo;
|
788 | BigInteger.prototype.squareTo = bnpSquareTo;
|
789 | BigInteger.prototype.divRemTo = bnpDivRemTo;
|
790 | BigInteger.prototype.invDigit = bnpInvDigit;
|
791 | BigInteger.prototype.addTo = bnpAddTo;
|
792 |
|
793 |
|
794 | BigInteger.prototype.toString = bnToString;
|
795 | BigInteger.prototype.negate = bnNegate;
|
796 | BigInteger.prototype.abs = bnAbs;
|
797 | BigInteger.prototype.compareTo = bnCompareTo;
|
798 | BigInteger.prototype.bitLength = bnBitLength;
|
799 | BigInteger.prototype.mod = bnMod;
|
800 | BigInteger.prototype.equals = bnEquals;
|
801 | BigInteger.prototype.add = bnAdd;
|
802 | BigInteger.prototype.subtract = bnSubtract;
|
803 | BigInteger.prototype.multiply = bnMultiply;
|
804 | BigInteger.prototype.divide = bnDivide;
|
805 | BigInteger.prototype.modPow = bnModPow;
|
806 |
|
807 |
|
808 | BigInteger.ZERO = nbv(0);
|
809 | BigInteger.ONE = nbv(1);
|