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