1 | (function(){
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
10 | var dbits;
|
11 |
|
12 |
|
13 | var canary = 0xdeadbeefcafe;
|
14 | var j_lm = ((canary&0xffffff)==0xefcafe);
|
15 |
|
16 |
|
17 | function BigInteger(a,b,c) {
|
18 | if(a != null)
|
19 | if("number" == typeof a) this.fromNumber(a,b,c);
|
20 | else if(b == null && "string" != typeof a) this.fromString(a,256);
|
21 | else this.fromString(a,b);
|
22 | }
|
23 |
|
24 |
|
25 | function nbi() { return new BigInteger(null); }
|
26 |
|
27 |
|
28 |
|
29 |
|
30 |
|
31 |
|
32 |
|
33 |
|
34 |
|
35 | function am1(i,x,w,j,c,n) {
|
36 | while(--n >= 0) {
|
37 | var v = x*this[i++]+w[j]+c;
|
38 | c = Math.floor(v/0x4000000);
|
39 | w[j++] = v&0x3ffffff;
|
40 | }
|
41 | return c;
|
42 | }
|
43 |
|
44 |
|
45 |
|
46 | function am2(i,x,w,j,c,n) {
|
47 | var xl = x&0x7fff, xh = x>>15;
|
48 | while(--n >= 0) {
|
49 | var l = this[i]&0x7fff;
|
50 | var h = this[i++]>>15;
|
51 | var m = xh*l+h*xl;
|
52 | l = xl*l+((m&0x7fff)<<15)+w[j]+(c&0x3fffffff);
|
53 | c = (l>>>30)+(m>>>15)+xh*h+(c>>>30);
|
54 | w[j++] = l&0x3fffffff;
|
55 | }
|
56 | return c;
|
57 | }
|
58 |
|
59 |
|
60 | function am3(i,x,w,j,c,n) {
|
61 | var xl = x&0x3fff, xh = x>>14;
|
62 | while(--n >= 0) {
|
63 | var l = this[i]&0x3fff;
|
64 | var h = this[i++]>>14;
|
65 | var m = xh*l+h*xl;
|
66 | l = xl*l+((m&0x3fff)<<14)+w[j]+c;
|
67 | c = (l>>28)+(m>>14)+xh*h;
|
68 | w[j++] = l&0xfffffff;
|
69 | }
|
70 | return c;
|
71 | }
|
72 | var inBrowser = typeof navigator !== "undefined";
|
73 | if(inBrowser && j_lm && (navigator.appName == "Microsoft Internet Explorer")) {
|
74 | BigInteger.prototype.am = am2;
|
75 | dbits = 30;
|
76 | }
|
77 | else if(inBrowser && j_lm && (navigator.appName != "Netscape")) {
|
78 | BigInteger.prototype.am = am1;
|
79 | dbits = 26;
|
80 | }
|
81 | else {
|
82 | BigInteger.prototype.am = am3;
|
83 | dbits = 28;
|
84 | }
|
85 |
|
86 | BigInteger.prototype.DB = dbits;
|
87 | BigInteger.prototype.DM = ((1<<dbits)-1);
|
88 | BigInteger.prototype.DV = (1<<dbits);
|
89 |
|
90 | var BI_FP = 52;
|
91 | BigInteger.prototype.FV = Math.pow(2,BI_FP);
|
92 | BigInteger.prototype.F1 = BI_FP-dbits;
|
93 | BigInteger.prototype.F2 = 2*dbits-BI_FP;
|
94 |
|
95 |
|
96 | var BI_RM = "0123456789abcdefghijklmnopqrstuvwxyz";
|
97 | var BI_RC = new Array();
|
98 | var rr,vv;
|
99 | rr = "0".charCodeAt(0);
|
100 | for(vv = 0; vv <= 9; ++vv) BI_RC[rr++] = vv;
|
101 | rr = "a".charCodeAt(0);
|
102 | for(vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv;
|
103 | rr = "A".charCodeAt(0);
|
104 | for(vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv;
|
105 |
|
106 | function int2char(n) { return BI_RM.charAt(n); }
|
107 | function intAt(s,i) {
|
108 | var c = BI_RC[s.charCodeAt(i)];
|
109 | return (c==null)?-1:c;
|
110 | }
|
111 |
|
112 |
|
113 | function bnpCopyTo(r) {
|
114 | for(var i = this.t-1; i >= 0; --i) r[i] = this[i];
|
115 | r.t = this.t;
|
116 | r.s = this.s;
|
117 | }
|
118 |
|
119 |
|
120 | function bnpFromInt(x) {
|
121 | this.t = 1;
|
122 | this.s = (x<0)?-1:0;
|
123 | if(x > 0) this[0] = x;
|
124 | else if(x < -1) this[0] = x+this.DV;
|
125 | else this.t = 0;
|
126 | }
|
127 |
|
128 |
|
129 | function nbv(i) { var r = nbi(); r.fromInt(i); return r; }
|
130 |
|
131 |
|
132 | function bnpFromString(s,b) {
|
133 | var k;
|
134 | if(b == 16) k = 4;
|
135 | else if(b == 8) k = 3;
|
136 | else if(b == 256) k = 8;
|
137 | else if(b == 2) k = 1;
|
138 | else if(b == 32) k = 5;
|
139 | else if(b == 4) k = 2;
|
140 | else { this.fromRadix(s,b); return; }
|
141 | this.t = 0;
|
142 | this.s = 0;
|
143 | var i = s.length, mi = false, sh = 0;
|
144 | while(--i >= 0) {
|
145 | var x = (k==8)?s[i]&0xff:intAt(s,i);
|
146 | if(x < 0) {
|
147 | if(s.charAt(i) == "-") mi = true;
|
148 | continue;
|
149 | }
|
150 | mi = false;
|
151 | if(sh == 0)
|
152 | this[this.t++] = x;
|
153 | else if(sh+k > this.DB) {
|
154 | this[this.t-1] |= (x&((1<<(this.DB-sh))-1))<<sh;
|
155 | this[this.t++] = (x>>(this.DB-sh));
|
156 | }
|
157 | else
|
158 | this[this.t-1] |= x<<sh;
|
159 | sh += k;
|
160 | if(sh >= this.DB) sh -= this.DB;
|
161 | }
|
162 | if(k == 8 && (s[0]&0x80) != 0) {
|
163 | this.s = -1;
|
164 | if(sh > 0) this[this.t-1] |= ((1<<(this.DB-sh))-1)<<sh;
|
165 | }
|
166 | this.clamp();
|
167 | if(mi) BigInteger.ZERO.subTo(this,this);
|
168 | }
|
169 |
|
170 |
|
171 | function bnpClamp() {
|
172 | var c = this.s&this.DM;
|
173 | while(this.t > 0 && this[this.t-1] == c) --this.t;
|
174 | }
|
175 |
|
176 |
|
177 | function bnToString(b) {
|
178 | if(this.s < 0) return "-"+this.negate().toString(b);
|
179 | var k;
|
180 | if(b == 16) k = 4;
|
181 | else if(b == 8) k = 3;
|
182 | else if(b == 2) k = 1;
|
183 | else if(b == 32) k = 5;
|
184 | else if(b == 4) k = 2;
|
185 | else return this.toRadix(b);
|
186 | var km = (1<<k)-1, d, m = false, r = "", i = this.t;
|
187 | var p = this.DB-(i*this.DB)%k;
|
188 | if(i-- > 0) {
|
189 | if(p < this.DB && (d = this[i]>>p) > 0) { m = true; r = int2char(d); }
|
190 | while(i >= 0) {
|
191 | if(p < k) {
|
192 | d = (this[i]&((1<<p)-1))<<(k-p);
|
193 | d |= this[--i]>>(p+=this.DB-k);
|
194 | }
|
195 | else {
|
196 | d = (this[i]>>(p-=k))&km;
|
197 | if(p <= 0) { p += this.DB; --i; }
|
198 | }
|
199 | if(d > 0) m = true;
|
200 | if(m) r += int2char(d);
|
201 | }
|
202 | }
|
203 | return m?r:"0";
|
204 | }
|
205 |
|
206 |
|
207 | function bnNegate() { var r = nbi(); BigInteger.ZERO.subTo(this,r); return r; }
|
208 |
|
209 |
|
210 | function bnAbs() { return (this.s<0)?this.negate():this; }
|
211 |
|
212 |
|
213 | function bnCompareTo(a) {
|
214 | var r = this.s-a.s;
|
215 | if(r != 0) return r;
|
216 | var i = this.t;
|
217 | r = i-a.t;
|
218 | if(r != 0) return (this.s<0)?-r:r;
|
219 | while(--i >= 0) if((r=this[i]-a[i]) != 0) return r;
|
220 | return 0;
|
221 | }
|
222 |
|
223 |
|
224 | function nbits(x) {
|
225 | var r = 1, t;
|
226 | if((t=x>>>16) != 0) { x = t; r += 16; }
|
227 | if((t=x>>8) != 0) { x = t; r += 8; }
|
228 | if((t=x>>4) != 0) { x = t; r += 4; }
|
229 | if((t=x>>2) != 0) { x = t; r += 2; }
|
230 | if((t=x>>1) != 0) { x = t; r += 1; }
|
231 | return r;
|
232 | }
|
233 |
|
234 |
|
235 | function bnBitLength() {
|
236 | if(this.t <= 0) return 0;
|
237 | return this.DB*(this.t-1)+nbits(this[this.t-1]^(this.s&this.DM));
|
238 | }
|
239 |
|
240 |
|
241 | function bnpDLShiftTo(n,r) {
|
242 | var i;
|
243 | for(i = this.t-1; i >= 0; --i) r[i+n] = this[i];
|
244 | for(i = n-1; i >= 0; --i) r[i] = 0;
|
245 | r.t = this.t+n;
|
246 | r.s = this.s;
|
247 | }
|
248 |
|
249 |
|
250 | function bnpDRShiftTo(n,r) {
|
251 | for(var i = n; i < this.t; ++i) r[i-n] = this[i];
|
252 | r.t = Math.max(this.t-n,0);
|
253 | r.s = this.s;
|
254 | }
|
255 |
|
256 |
|
257 | function bnpLShiftTo(n,r) {
|
258 | var bs = n%this.DB;
|
259 | var cbs = this.DB-bs;
|
260 | var bm = (1<<cbs)-1;
|
261 | var ds = Math.floor(n/this.DB), c = (this.s<<bs)&this.DM, i;
|
262 | for(i = this.t-1; i >= 0; --i) {
|
263 | r[i+ds+1] = (this[i]>>cbs)|c;
|
264 | c = (this[i]&bm)<<bs;
|
265 | }
|
266 | for(i = ds-1; i >= 0; --i) r[i] = 0;
|
267 | r[ds] = c;
|
268 | r.t = this.t+ds+1;
|
269 | r.s = this.s;
|
270 | r.clamp();
|
271 | }
|
272 |
|
273 |
|
274 | function bnpRShiftTo(n,r) {
|
275 | r.s = this.s;
|
276 | var ds = Math.floor(n/this.DB);
|
277 | if(ds >= this.t) { r.t = 0; return; }
|
278 | var bs = n%this.DB;
|
279 | var cbs = this.DB-bs;
|
280 | var bm = (1<<bs)-1;
|
281 | r[0] = this[ds]>>bs;
|
282 | for(var i = ds+1; i < this.t; ++i) {
|
283 | r[i-ds-1] |= (this[i]&bm)<<cbs;
|
284 | r[i-ds] = this[i]>>bs;
|
285 | }
|
286 | if(bs > 0) r[this.t-ds-1] |= (this.s&bm)<<cbs;
|
287 | r.t = this.t-ds;
|
288 | r.clamp();
|
289 | }
|
290 |
|
291 |
|
292 | function bnpSubTo(a,r) {
|
293 | var i = 0, c = 0, m = Math.min(a.t,this.t);
|
294 | while(i < m) {
|
295 | c += this[i]-a[i];
|
296 | r[i++] = c&this.DM;
|
297 | c >>= this.DB;
|
298 | }
|
299 | if(a.t < this.t) {
|
300 | c -= a.s;
|
301 | while(i < this.t) {
|
302 | c += this[i];
|
303 | r[i++] = c&this.DM;
|
304 | c >>= this.DB;
|
305 | }
|
306 | c += this.s;
|
307 | }
|
308 | else {
|
309 | c += this.s;
|
310 | while(i < a.t) {
|
311 | c -= a[i];
|
312 | r[i++] = c&this.DM;
|
313 | c >>= this.DB;
|
314 | }
|
315 | c -= a.s;
|
316 | }
|
317 | r.s = (c<0)?-1:0;
|
318 | if(c < -1) r[i++] = this.DV+c;
|
319 | else if(c > 0) r[i++] = c;
|
320 | r.t = i;
|
321 | r.clamp();
|
322 | }
|
323 |
|
324 |
|
325 |
|
326 | function bnpMultiplyTo(a,r) {
|
327 | var x = this.abs(), y = a.abs();
|
328 | var i = x.t;
|
329 | r.t = i+y.t;
|
330 | while(--i >= 0) r[i] = 0;
|
331 | for(i = 0; i < y.t; ++i) r[i+x.t] = x.am(0,y[i],r,i,0,x.t);
|
332 | r.s = 0;
|
333 | r.clamp();
|
334 | if(this.s != a.s) BigInteger.ZERO.subTo(r,r);
|
335 | }
|
336 |
|
337 |
|
338 | function bnpSquareTo(r) {
|
339 | var x = this.abs();
|
340 | var i = r.t = 2*x.t;
|
341 | while(--i >= 0) r[i] = 0;
|
342 | for(i = 0; i < x.t-1; ++i) {
|
343 | var c = x.am(i,x[i],r,2*i,0,1);
|
344 | if((r[i+x.t]+=x.am(i+1,2*x[i],r,2*i+1,c,x.t-i-1)) >= x.DV) {
|
345 | r[i+x.t] -= x.DV;
|
346 | r[i+x.t+1] = 1;
|
347 | }
|
348 | }
|
349 | if(r.t > 0) r[r.t-1] += x.am(i,x[i],r,2*i,0,1);
|
350 | r.s = 0;
|
351 | r.clamp();
|
352 | }
|
353 |
|
354 |
|
355 |
|
356 | function bnpDivRemTo(m,q,r) {
|
357 | var pm = m.abs();
|
358 | if(pm.t <= 0) return;
|
359 | var pt = this.abs();
|
360 | if(pt.t < pm.t) {
|
361 | if(q != null) q.fromInt(0);
|
362 | if(r != null) this.copyTo(r);
|
363 | return;
|
364 | }
|
365 | if(r == null) r = nbi();
|
366 | var y = nbi(), ts = this.s, ms = m.s;
|
367 | var nsh = this.DB-nbits(pm[pm.t-1]);
|
368 | if(nsh > 0) { pm.lShiftTo(nsh,y); pt.lShiftTo(nsh,r); }
|
369 | else { pm.copyTo(y); pt.copyTo(r); }
|
370 | var ys = y.t;
|
371 | var y0 = y[ys-1];
|
372 | if(y0 == 0) return;
|
373 | var yt = y0*(1<<this.F1)+((ys>1)?y[ys-2]>>this.F2:0);
|
374 | var d1 = this.FV/yt, d2 = (1<<this.F1)/yt, e = 1<<this.F2;
|
375 | var i = r.t, j = i-ys, t = (q==null)?nbi():q;
|
376 | y.dlShiftTo(j,t);
|
377 | if(r.compareTo(t) >= 0) {
|
378 | r[r.t++] = 1;
|
379 | r.subTo(t,r);
|
380 | }
|
381 | BigInteger.ONE.dlShiftTo(ys,t);
|
382 | t.subTo(y,y);
|
383 | while(y.t < ys) y[y.t++] = 0;
|
384 | while(--j >= 0) {
|
385 |
|
386 | var qd = (r[--i]==y0)?this.DM:Math.floor(r[i]*d1+(r[i-1]+e)*d2);
|
387 | if((r[i]+=y.am(0,qd,r,j,0,ys)) < qd) {
|
388 | y.dlShiftTo(j,t);
|
389 | r.subTo(t,r);
|
390 | while(r[i] < --qd) r.subTo(t,r);
|
391 | }
|
392 | }
|
393 | if(q != null) {
|
394 | r.drShiftTo(ys,q);
|
395 | if(ts != ms) BigInteger.ZERO.subTo(q,q);
|
396 | }
|
397 | r.t = ys;
|
398 | r.clamp();
|
399 | if(nsh > 0) r.rShiftTo(nsh,r);
|
400 | if(ts < 0) BigInteger.ZERO.subTo(r,r);
|
401 | }
|
402 |
|
403 |
|
404 | function bnMod(a) {
|
405 | var r = nbi();
|
406 | this.abs().divRemTo(a,null,r);
|
407 | if(this.s < 0 && r.compareTo(BigInteger.ZERO) > 0) a.subTo(r,r);
|
408 | return r;
|
409 | }
|
410 |
|
411 |
|
412 | function Classic(m) { this.m = m; }
|
413 | function cConvert(x) {
|
414 | if(x.s < 0 || x.compareTo(this.m) >= 0) return x.mod(this.m);
|
415 | else return x;
|
416 | }
|
417 | function cRevert(x) { return x; }
|
418 | function cReduce(x) { x.divRemTo(this.m,null,x); }
|
419 | function cMulTo(x,y,r) { x.multiplyTo(y,r); this.reduce(r); }
|
420 | function cSqrTo(x,r) { x.squareTo(r); this.reduce(r); }
|
421 |
|
422 | Classic.prototype.convert = cConvert;
|
423 | Classic.prototype.revert = cRevert;
|
424 | Classic.prototype.reduce = cReduce;
|
425 | Classic.prototype.mulTo = cMulTo;
|
426 | Classic.prototype.sqrTo = cSqrTo;
|
427 |
|
428 |
|
429 |
|
430 |
|
431 |
|
432 |
|
433 |
|
434 |
|
435 |
|
436 |
|
437 |
|
438 | function bnpInvDigit() {
|
439 | if(this.t < 1) return 0;
|
440 | var x = this[0];
|
441 | if((x&1) == 0) return 0;
|
442 | var y = x&3;
|
443 | y = (y*(2-(x&0xf)*y))&0xf;
|
444 | y = (y*(2-(x&0xff)*y))&0xff;
|
445 | y = (y*(2-(((x&0xffff)*y)&0xffff)))&0xffff;
|
446 |
|
447 |
|
448 | y = (y*(2-x*y%this.DV))%this.DV;
|
449 |
|
450 | return (y>0)?this.DV-y:-y;
|
451 | }
|
452 |
|
453 |
|
454 | function Montgomery(m) {
|
455 | this.m = m;
|
456 | this.mp = m.invDigit();
|
457 | this.mpl = this.mp&0x7fff;
|
458 | this.mph = this.mp>>15;
|
459 | this.um = (1<<(m.DB-15))-1;
|
460 | this.mt2 = 2*m.t;
|
461 | }
|
462 |
|
463 |
|
464 | function montConvert(x) {
|
465 | var r = nbi();
|
466 | x.abs().dlShiftTo(this.m.t,r);
|
467 | r.divRemTo(this.m,null,r);
|
468 | if(x.s < 0 && r.compareTo(BigInteger.ZERO) > 0) this.m.subTo(r,r);
|
469 | return r;
|
470 | }
|
471 |
|
472 |
|
473 | function montRevert(x) {
|
474 | var r = nbi();
|
475 | x.copyTo(r);
|
476 | this.reduce(r);
|
477 | return r;
|
478 | }
|
479 |
|
480 |
|
481 | function montReduce(x) {
|
482 | while(x.t <= this.mt2)
|
483 | x[x.t++] = 0;
|
484 | for(var i = 0; i < this.m.t; ++i) {
|
485 |
|
486 | var j = x[i]&0x7fff;
|
487 | var u0 = (j*this.mpl+(((j*this.mph+(x[i]>>15)*this.mpl)&this.um)<<15))&x.DM;
|
488 |
|
489 | j = i+this.m.t;
|
490 | x[j] += this.m.am(0,u0,x,i,0,this.m.t);
|
491 |
|
492 | while(x[j] >= x.DV) { x[j] -= x.DV; x[++j]++; }
|
493 | }
|
494 | x.clamp();
|
495 | x.drShiftTo(this.m.t,x);
|
496 | if(x.compareTo(this.m) >= 0) x.subTo(this.m,x);
|
497 | }
|
498 |
|
499 |
|
500 | function montSqrTo(x,r) { x.squareTo(r); this.reduce(r); }
|
501 |
|
502 |
|
503 | function montMulTo(x,y,r) { x.multiplyTo(y,r); this.reduce(r); }
|
504 |
|
505 | Montgomery.prototype.convert = montConvert;
|
506 | Montgomery.prototype.revert = montRevert;
|
507 | Montgomery.prototype.reduce = montReduce;
|
508 | Montgomery.prototype.mulTo = montMulTo;
|
509 | Montgomery.prototype.sqrTo = montSqrTo;
|
510 |
|
511 |
|
512 | function bnpIsEven() { return ((this.t>0)?(this[0]&1):this.s) == 0; }
|
513 |
|
514 |
|
515 | function bnpExp(e,z) {
|
516 | if(e > 0xffffffff || e < 1) return BigInteger.ONE;
|
517 | var r = nbi(), r2 = nbi(), g = z.convert(this), i = nbits(e)-1;
|
518 | g.copyTo(r);
|
519 | while(--i >= 0) {
|
520 | z.sqrTo(r,r2);
|
521 | if((e&(1<<i)) > 0) z.mulTo(r2,g,r);
|
522 | else { var t = r; r = r2; r2 = t; }
|
523 | }
|
524 | return z.revert(r);
|
525 | }
|
526 |
|
527 |
|
528 | function bnModPowInt(e,m) {
|
529 | var z;
|
530 | if(e < 256 || m.isEven()) z = new Classic(m); else z = new Montgomery(m);
|
531 | return this.exp(e,z);
|
532 | }
|
533 |
|
534 |
|
535 | BigInteger.prototype.copyTo = bnpCopyTo;
|
536 | BigInteger.prototype.fromInt = bnpFromInt;
|
537 | BigInteger.prototype.fromString = bnpFromString;
|
538 | BigInteger.prototype.clamp = bnpClamp;
|
539 | BigInteger.prototype.dlShiftTo = bnpDLShiftTo;
|
540 | BigInteger.prototype.drShiftTo = bnpDRShiftTo;
|
541 | BigInteger.prototype.lShiftTo = bnpLShiftTo;
|
542 | BigInteger.prototype.rShiftTo = bnpRShiftTo;
|
543 | BigInteger.prototype.subTo = bnpSubTo;
|
544 | BigInteger.prototype.multiplyTo = bnpMultiplyTo;
|
545 | BigInteger.prototype.squareTo = bnpSquareTo;
|
546 | BigInteger.prototype.divRemTo = bnpDivRemTo;
|
547 | BigInteger.prototype.invDigit = bnpInvDigit;
|
548 | BigInteger.prototype.isEven = bnpIsEven;
|
549 | BigInteger.prototype.exp = bnpExp;
|
550 |
|
551 |
|
552 | BigInteger.prototype.toString = bnToString;
|
553 | BigInteger.prototype.negate = bnNegate;
|
554 | BigInteger.prototype.abs = bnAbs;
|
555 | BigInteger.prototype.compareTo = bnCompareTo;
|
556 | BigInteger.prototype.bitLength = bnBitLength;
|
557 | BigInteger.prototype.mod = bnMod;
|
558 | BigInteger.prototype.modPowInt = bnModPowInt;
|
559 |
|
560 |
|
561 | BigInteger.ZERO = nbv(0);
|
562 | BigInteger.ONE = nbv(1);
|
563 |
|
564 |
|
565 |
|
566 |
|
567 |
|
568 |
|
569 |
|
570 |
|
571 |
|
572 |
|
573 |
|
574 | function bnClone() { var r = nbi(); this.copyTo(r); return r; }
|
575 |
|
576 |
|
577 | function bnIntValue() {
|
578 | if(this.s < 0) {
|
579 | if(this.t == 1) return this[0]-this.DV;
|
580 | else if(this.t == 0) return -1;
|
581 | }
|
582 | else if(this.t == 1) return this[0];
|
583 | else if(this.t == 0) return 0;
|
584 |
|
585 | return ((this[1]&((1<<(32-this.DB))-1))<<this.DB)|this[0];
|
586 | }
|
587 |
|
588 |
|
589 | function bnByteValue() { return (this.t==0)?this.s:(this[0]<<24)>>24; }
|
590 |
|
591 |
|
592 | function bnShortValue() { return (this.t==0)?this.s:(this[0]<<16)>>16; }
|
593 |
|
594 |
|
595 | function bnpChunkSize(r) { return Math.floor(Math.LN2*this.DB/Math.log(r)); }
|
596 |
|
597 |
|
598 | function bnSigNum() {
|
599 | if(this.s < 0) return -1;
|
600 | else if(this.t <= 0 || (this.t == 1 && this[0] <= 0)) return 0;
|
601 | else return 1;
|
602 | }
|
603 |
|
604 |
|
605 | function bnpToRadix(b) {
|
606 | if(b == null) b = 10;
|
607 | if(this.signum() == 0 || b < 2 || b > 36) return "0";
|
608 | var cs = this.chunkSize(b);
|
609 | var a = Math.pow(b,cs);
|
610 | var d = nbv(a), y = nbi(), z = nbi(), r = "";
|
611 | this.divRemTo(d,y,z);
|
612 | while(y.signum() > 0) {
|
613 | r = (a+z.intValue()).toString(b).substr(1) + r;
|
614 | y.divRemTo(d,y,z);
|
615 | }
|
616 | return z.intValue().toString(b) + r;
|
617 | }
|
618 |
|
619 |
|
620 | function bnpFromRadix(s,b) {
|
621 | this.fromInt(0);
|
622 | if(b == null) b = 10;
|
623 | var cs = this.chunkSize(b);
|
624 | var d = Math.pow(b,cs), mi = false, j = 0, w = 0;
|
625 | for(var i = 0; i < s.length; ++i) {
|
626 | var x = intAt(s,i);
|
627 | if(x < 0) {
|
628 | if(s.charAt(i) == "-" && this.signum() == 0) mi = true;
|
629 | continue;
|
630 | }
|
631 | w = b*w+x;
|
632 | if(++j >= cs) {
|
633 | this.dMultiply(d);
|
634 | this.dAddOffset(w,0);
|
635 | j = 0;
|
636 | w = 0;
|
637 | }
|
638 | }
|
639 | if(j > 0) {
|
640 | this.dMultiply(Math.pow(b,j));
|
641 | this.dAddOffset(w,0);
|
642 | }
|
643 | if(mi) BigInteger.ZERO.subTo(this,this);
|
644 | }
|
645 |
|
646 |
|
647 | function bnpFromNumber(a,b,c) {
|
648 | if("number" == typeof b) {
|
649 |
|
650 | if(a < 2) this.fromInt(1);
|
651 | else {
|
652 | this.fromNumber(a,c);
|
653 | if(!this.testBit(a-1))
|
654 | this.bitwiseTo(BigInteger.ONE.shiftLeft(a-1),op_or,this);
|
655 | if(this.isEven()) this.dAddOffset(1,0);
|
656 | while(!this.isProbablePrime(b)) {
|
657 | this.dAddOffset(2,0);
|
658 | if(this.bitLength() > a) this.subTo(BigInteger.ONE.shiftLeft(a-1),this);
|
659 | }
|
660 | }
|
661 | }
|
662 | else {
|
663 |
|
664 | var x = new Array(), t = a&7;
|
665 | x.length = (a>>3)+1;
|
666 | b.nextBytes(x);
|
667 | if(t > 0) x[0] &= ((1<<t)-1); else x[0] = 0;
|
668 | this.fromString(x,256);
|
669 | }
|
670 | }
|
671 |
|
672 |
|
673 | function bnToByteArray() {
|
674 | var i = this.t, r = new Array();
|
675 | r[0] = this.s;
|
676 | var p = this.DB-(i*this.DB)%8, d, k = 0;
|
677 | if(i-- > 0) {
|
678 | if(p < this.DB && (d = this[i]>>p) != (this.s&this.DM)>>p)
|
679 | r[k++] = d|(this.s<<(this.DB-p));
|
680 | while(i >= 0) {
|
681 | if(p < 8) {
|
682 | d = (this[i]&((1<<p)-1))<<(8-p);
|
683 | d |= this[--i]>>(p+=this.DB-8);
|
684 | }
|
685 | else {
|
686 | d = (this[i]>>(p-=8))&0xff;
|
687 | if(p <= 0) { p += this.DB; --i; }
|
688 | }
|
689 | if((d&0x80) != 0) d |= -256;
|
690 | if(k == 0 && (this.s&0x80) != (d&0x80)) ++k;
|
691 | if(k > 0 || d != this.s) r[k++] = d;
|
692 | }
|
693 | }
|
694 | return r;
|
695 | }
|
696 |
|
697 | function bnEquals(a) { return(this.compareTo(a)==0); }
|
698 | function bnMin(a) { return(this.compareTo(a)<0)?this:a; }
|
699 | function bnMax(a) { return(this.compareTo(a)>0)?this:a; }
|
700 |
|
701 |
|
702 | function bnpBitwiseTo(a,op,r) {
|
703 | var i, f, m = Math.min(a.t,this.t);
|
704 | for(i = 0; i < m; ++i) r[i] = op(this[i],a[i]);
|
705 | if(a.t < this.t) {
|
706 | f = a.s&this.DM;
|
707 | for(i = m; i < this.t; ++i) r[i] = op(this[i],f);
|
708 | r.t = this.t;
|
709 | }
|
710 | else {
|
711 | f = this.s&this.DM;
|
712 | for(i = m; i < a.t; ++i) r[i] = op(f,a[i]);
|
713 | r.t = a.t;
|
714 | }
|
715 | r.s = op(this.s,a.s);
|
716 | r.clamp();
|
717 | }
|
718 |
|
719 |
|
720 | function op_and(x,y) { return x&y; }
|
721 | function bnAnd(a) { var r = nbi(); this.bitwiseTo(a,op_and,r); return r; }
|
722 |
|
723 |
|
724 | function op_or(x,y) { return x|y; }
|
725 | function bnOr(a) { var r = nbi(); this.bitwiseTo(a,op_or,r); return r; }
|
726 |
|
727 |
|
728 | function op_xor(x,y) { return x^y; }
|
729 | function bnXor(a) { var r = nbi(); this.bitwiseTo(a,op_xor,r); return r; }
|
730 |
|
731 |
|
732 | function op_andnot(x,y) { return x&~y; }
|
733 | function bnAndNot(a) { var r = nbi(); this.bitwiseTo(a,op_andnot,r); return r; }
|
734 |
|
735 |
|
736 | function bnNot() {
|
737 | var r = nbi();
|
738 | for(var i = 0; i < this.t; ++i) r[i] = this.DM&~this[i];
|
739 | r.t = this.t;
|
740 | r.s = ~this.s;
|
741 | return r;
|
742 | }
|
743 |
|
744 |
|
745 | function bnShiftLeft(n) {
|
746 | var r = nbi();
|
747 | if(n < 0) this.rShiftTo(-n,r); else this.lShiftTo(n,r);
|
748 | return r;
|
749 | }
|
750 |
|
751 |
|
752 | function bnShiftRight(n) {
|
753 | var r = nbi();
|
754 | if(n < 0) this.lShiftTo(-n,r); else this.rShiftTo(n,r);
|
755 | return r;
|
756 | }
|
757 |
|
758 |
|
759 | function lbit(x) {
|
760 | if(x == 0) return -1;
|
761 | var r = 0;
|
762 | if((x&0xffff) == 0) { x >>= 16; r += 16; }
|
763 | if((x&0xff) == 0) { x >>= 8; r += 8; }
|
764 | if((x&0xf) == 0) { x >>= 4; r += 4; }
|
765 | if((x&3) == 0) { x >>= 2; r += 2; }
|
766 | if((x&1) == 0) ++r;
|
767 | return r;
|
768 | }
|
769 |
|
770 |
|
771 | function bnGetLowestSetBit() {
|
772 | for(var i = 0; i < this.t; ++i)
|
773 | if(this[i] != 0) return i*this.DB+lbit(this[i]);
|
774 | if(this.s < 0) return this.t*this.DB;
|
775 | return -1;
|
776 | }
|
777 |
|
778 |
|
779 | function cbit(x) {
|
780 | var r = 0;
|
781 | while(x != 0) { x &= x-1; ++r; }
|
782 | return r;
|
783 | }
|
784 |
|
785 |
|
786 | function bnBitCount() {
|
787 | var r = 0, x = this.s&this.DM;
|
788 | for(var i = 0; i < this.t; ++i) r += cbit(this[i]^x);
|
789 | return r;
|
790 | }
|
791 |
|
792 |
|
793 | function bnTestBit(n) {
|
794 | var j = Math.floor(n/this.DB);
|
795 | if(j >= this.t) return(this.s!=0);
|
796 | return((this[j]&(1<<(n%this.DB)))!=0);
|
797 | }
|
798 |
|
799 |
|
800 | function bnpChangeBit(n,op) {
|
801 | var r = BigInteger.ONE.shiftLeft(n);
|
802 | this.bitwiseTo(r,op,r);
|
803 | return r;
|
804 | }
|
805 |
|
806 |
|
807 | function bnSetBit(n) { return this.changeBit(n,op_or); }
|
808 |
|
809 |
|
810 | function bnClearBit(n) { return this.changeBit(n,op_andnot); }
|
811 |
|
812 |
|
813 | function bnFlipBit(n) { return this.changeBit(n,op_xor); }
|
814 |
|
815 |
|
816 | function bnpAddTo(a,r) {
|
817 | var i = 0, c = 0, m = Math.min(a.t,this.t);
|
818 | while(i < m) {
|
819 | c += this[i]+a[i];
|
820 | r[i++] = c&this.DM;
|
821 | c >>= this.DB;
|
822 | }
|
823 | if(a.t < this.t) {
|
824 | c += a.s;
|
825 | while(i < this.t) {
|
826 | c += this[i];
|
827 | r[i++] = c&this.DM;
|
828 | c >>= this.DB;
|
829 | }
|
830 | c += this.s;
|
831 | }
|
832 | else {
|
833 | c += this.s;
|
834 | while(i < a.t) {
|
835 | c += a[i];
|
836 | r[i++] = c&this.DM;
|
837 | c >>= this.DB;
|
838 | }
|
839 | c += a.s;
|
840 | }
|
841 | r.s = (c<0)?-1:0;
|
842 | if(c > 0) r[i++] = c;
|
843 | else if(c < -1) r[i++] = this.DV+c;
|
844 | r.t = i;
|
845 | r.clamp();
|
846 | }
|
847 |
|
848 |
|
849 | function bnAdd(a) { var r = nbi(); this.addTo(a,r); return r; }
|
850 |
|
851 |
|
852 | function bnSubtract(a) { var r = nbi(); this.subTo(a,r); return r; }
|
853 |
|
854 |
|
855 | function bnMultiply(a) { var r = nbi(); this.multiplyTo(a,r); return r; }
|
856 |
|
857 |
|
858 | function bnSquare() { var r = nbi(); this.squareTo(r); return r; }
|
859 |
|
860 |
|
861 | function bnDivide(a) { var r = nbi(); this.divRemTo(a,r,null); return r; }
|
862 |
|
863 |
|
864 | function bnRemainder(a) { var r = nbi(); this.divRemTo(a,null,r); return r; }
|
865 |
|
866 |
|
867 | function bnDivideAndRemainder(a) {
|
868 | var q = nbi(), r = nbi();
|
869 | this.divRemTo(a,q,r);
|
870 | return new Array(q,r);
|
871 | }
|
872 |
|
873 |
|
874 | function bnpDMultiply(n) {
|
875 | this[this.t] = this.am(0,n-1,this,0,0,this.t);
|
876 | ++this.t;
|
877 | this.clamp();
|
878 | }
|
879 |
|
880 |
|
881 | function bnpDAddOffset(n,w) {
|
882 | if(n == 0) return;
|
883 | while(this.t <= w) this[this.t++] = 0;
|
884 | this[w] += n;
|
885 | while(this[w] >= this.DV) {
|
886 | this[w] -= this.DV;
|
887 | if(++w >= this.t) this[this.t++] = 0;
|
888 | ++this[w];
|
889 | }
|
890 | }
|
891 |
|
892 |
|
893 | function NullExp() {}
|
894 | function nNop(x) { return x; }
|
895 | function nMulTo(x,y,r) { x.multiplyTo(y,r); }
|
896 | function nSqrTo(x,r) { x.squareTo(r); }
|
897 |
|
898 | NullExp.prototype.convert = nNop;
|
899 | NullExp.prototype.revert = nNop;
|
900 | NullExp.prototype.mulTo = nMulTo;
|
901 | NullExp.prototype.sqrTo = nSqrTo;
|
902 |
|
903 |
|
904 | function bnPow(e) { return this.exp(e,new NullExp()); }
|
905 |
|
906 |
|
907 |
|
908 | function bnpMultiplyLowerTo(a,n,r) {
|
909 | var i = Math.min(this.t+a.t,n);
|
910 | r.s = 0;
|
911 | r.t = i;
|
912 | while(i > 0) r[--i] = 0;
|
913 | var j;
|
914 | for(j = r.t-this.t; i < j; ++i) r[i+this.t] = this.am(0,a[i],r,i,0,this.t);
|
915 | for(j = Math.min(a.t,n); i < j; ++i) this.am(0,a[i],r,i,0,n-i);
|
916 | r.clamp();
|
917 | }
|
918 |
|
919 |
|
920 |
|
921 | function bnpMultiplyUpperTo(a,n,r) {
|
922 | --n;
|
923 | var i = r.t = this.t+a.t-n;
|
924 | r.s = 0;
|
925 | while(--i >= 0) r[i] = 0;
|
926 | for(i = Math.max(n-this.t,0); i < a.t; ++i)
|
927 | r[this.t+i-n] = this.am(n-i,a[i],r,0,0,this.t+i-n);
|
928 | r.clamp();
|
929 | r.drShiftTo(1,r);
|
930 | }
|
931 |
|
932 |
|
933 | function Barrett(m) {
|
934 |
|
935 | this.r2 = nbi();
|
936 | this.q3 = nbi();
|
937 | BigInteger.ONE.dlShiftTo(2*m.t,this.r2);
|
938 | this.mu = this.r2.divide(m);
|
939 | this.m = m;
|
940 | }
|
941 |
|
942 | function barrettConvert(x) {
|
943 | if(x.s < 0 || x.t > 2*this.m.t) return x.mod(this.m);
|
944 | else if(x.compareTo(this.m) < 0) return x;
|
945 | else { var r = nbi(); x.copyTo(r); this.reduce(r); return r; }
|
946 | }
|
947 |
|
948 | function barrettRevert(x) { return x; }
|
949 |
|
950 |
|
951 | function barrettReduce(x) {
|
952 | x.drShiftTo(this.m.t-1,this.r2);
|
953 | if(x.t > this.m.t+1) { x.t = this.m.t+1; x.clamp(); }
|
954 | this.mu.multiplyUpperTo(this.r2,this.m.t+1,this.q3);
|
955 | this.m.multiplyLowerTo(this.q3,this.m.t+1,this.r2);
|
956 | while(x.compareTo(this.r2) < 0) x.dAddOffset(1,this.m.t+1);
|
957 | x.subTo(this.r2,x);
|
958 | while(x.compareTo(this.m) >= 0) x.subTo(this.m,x);
|
959 | }
|
960 |
|
961 |
|
962 | function barrettSqrTo(x,r) { x.squareTo(r); this.reduce(r); }
|
963 |
|
964 |
|
965 | function barrettMulTo(x,y,r) { x.multiplyTo(y,r); this.reduce(r); }
|
966 |
|
967 | Barrett.prototype.convert = barrettConvert;
|
968 | Barrett.prototype.revert = barrettRevert;
|
969 | Barrett.prototype.reduce = barrettReduce;
|
970 | Barrett.prototype.mulTo = barrettMulTo;
|
971 | Barrett.prototype.sqrTo = barrettSqrTo;
|
972 |
|
973 |
|
974 | function bnModPow(e,m) {
|
975 | var i = e.bitLength(), k, r = nbv(1), z;
|
976 | if(i <= 0) return r;
|
977 | else if(i < 18) k = 1;
|
978 | else if(i < 48) k = 3;
|
979 | else if(i < 144) k = 4;
|
980 | else if(i < 768) k = 5;
|
981 | else k = 6;
|
982 | if(i < 8)
|
983 | z = new Classic(m);
|
984 | else if(m.isEven())
|
985 | z = new Barrett(m);
|
986 | else
|
987 | z = new Montgomery(m);
|
988 |
|
989 |
|
990 | var g = new Array(), n = 3, k1 = k-1, km = (1<<k)-1;
|
991 | g[1] = z.convert(this);
|
992 | if(k > 1) {
|
993 | var g2 = nbi();
|
994 | z.sqrTo(g[1],g2);
|
995 | while(n <= km) {
|
996 | g[n] = nbi();
|
997 | z.mulTo(g2,g[n-2],g[n]);
|
998 | n += 2;
|
999 | }
|
1000 | }
|
1001 |
|
1002 | var j = e.t-1, w, is1 = true, r2 = nbi(), t;
|
1003 | i = nbits(e[j])-1;
|
1004 | while(j >= 0) {
|
1005 | if(i >= k1) w = (e[j]>>(i-k1))&km;
|
1006 | else {
|
1007 | w = (e[j]&((1<<(i+1))-1))<<(k1-i);
|
1008 | if(j > 0) w |= e[j-1]>>(this.DB+i-k1);
|
1009 | }
|
1010 |
|
1011 | n = k;
|
1012 | while((w&1) == 0) { w >>= 1; --n; }
|
1013 | if((i -= n) < 0) { i += this.DB; --j; }
|
1014 | if(is1) {
|
1015 | g[w].copyTo(r);
|
1016 | is1 = false;
|
1017 | }
|
1018 | else {
|
1019 | while(n > 1) { z.sqrTo(r,r2); z.sqrTo(r2,r); n -= 2; }
|
1020 | if(n > 0) z.sqrTo(r,r2); else { t = r; r = r2; r2 = t; }
|
1021 | z.mulTo(r2,g[w],r);
|
1022 | }
|
1023 |
|
1024 | while(j >= 0 && (e[j]&(1<<i)) == 0) {
|
1025 | z.sqrTo(r,r2); t = r; r = r2; r2 = t;
|
1026 | if(--i < 0) { i = this.DB-1; --j; }
|
1027 | }
|
1028 | }
|
1029 | return z.revert(r);
|
1030 | }
|
1031 |
|
1032 |
|
1033 | function bnGCD(a) {
|
1034 | var x = (this.s<0)?this.negate():this.clone();
|
1035 | var y = (a.s<0)?a.negate():a.clone();
|
1036 | if(x.compareTo(y) < 0) { var t = x; x = y; y = t; }
|
1037 | var i = x.getLowestSetBit(), g = y.getLowestSetBit();
|
1038 | if(g < 0) return x;
|
1039 | if(i < g) g = i;
|
1040 | if(g > 0) {
|
1041 | x.rShiftTo(g,x);
|
1042 | y.rShiftTo(g,y);
|
1043 | }
|
1044 | while(x.signum() > 0) {
|
1045 | if((i = x.getLowestSetBit()) > 0) x.rShiftTo(i,x);
|
1046 | if((i = y.getLowestSetBit()) > 0) y.rShiftTo(i,y);
|
1047 | if(x.compareTo(y) >= 0) {
|
1048 | x.subTo(y,x);
|
1049 | x.rShiftTo(1,x);
|
1050 | }
|
1051 | else {
|
1052 | y.subTo(x,y);
|
1053 | y.rShiftTo(1,y);
|
1054 | }
|
1055 | }
|
1056 | if(g > 0) y.lShiftTo(g,y);
|
1057 | return y;
|
1058 | }
|
1059 |
|
1060 |
|
1061 | function bnpModInt(n) {
|
1062 | if(n <= 0) return 0;
|
1063 | var d = this.DV%n, r = (this.s<0)?n-1:0;
|
1064 | if(this.t > 0)
|
1065 | if(d == 0) r = this[0]%n;
|
1066 | else for(var i = this.t-1; i >= 0; --i) r = (d*r+this[i])%n;
|
1067 | return r;
|
1068 | }
|
1069 |
|
1070 |
|
1071 | function bnModInverse(m) {
|
1072 | var ac = m.isEven();
|
1073 | if((this.isEven() && ac) || m.signum() == 0) return BigInteger.ZERO;
|
1074 | var u = m.clone(), v = this.clone();
|
1075 | var a = nbv(1), b = nbv(0), c = nbv(0), d = nbv(1);
|
1076 | while(u.signum() != 0) {
|
1077 | while(u.isEven()) {
|
1078 | u.rShiftTo(1,u);
|
1079 | if(ac) {
|
1080 | if(!a.isEven() || !b.isEven()) { a.addTo(this,a); b.subTo(m,b); }
|
1081 | a.rShiftTo(1,a);
|
1082 | }
|
1083 | else if(!b.isEven()) b.subTo(m,b);
|
1084 | b.rShiftTo(1,b);
|
1085 | }
|
1086 | while(v.isEven()) {
|
1087 | v.rShiftTo(1,v);
|
1088 | if(ac) {
|
1089 | if(!c.isEven() || !d.isEven()) { c.addTo(this,c); d.subTo(m,d); }
|
1090 | c.rShiftTo(1,c);
|
1091 | }
|
1092 | else if(!d.isEven()) d.subTo(m,d);
|
1093 | d.rShiftTo(1,d);
|
1094 | }
|
1095 | if(u.compareTo(v) >= 0) {
|
1096 | u.subTo(v,u);
|
1097 | if(ac) a.subTo(c,a);
|
1098 | b.subTo(d,b);
|
1099 | }
|
1100 | else {
|
1101 | v.subTo(u,v);
|
1102 | if(ac) c.subTo(a,c);
|
1103 | d.subTo(b,d);
|
1104 | }
|
1105 | }
|
1106 | if(v.compareTo(BigInteger.ONE) != 0) return BigInteger.ZERO;
|
1107 | if(d.compareTo(m) >= 0) return d.subtract(m);
|
1108 | if(d.signum() < 0) d.addTo(m,d); else return d;
|
1109 | if(d.signum() < 0) return d.add(m); else return d;
|
1110 | }
|
1111 |
|
1112 | var lowprimes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997];
|
1113 | var lplim = (1<<26)/lowprimes[lowprimes.length-1];
|
1114 |
|
1115 |
|
1116 | function bnIsProbablePrime(t) {
|
1117 | var i, x = this.abs();
|
1118 | if(x.t == 1 && x[0] <= lowprimes[lowprimes.length-1]) {
|
1119 | for(i = 0; i < lowprimes.length; ++i)
|
1120 | if(x[0] == lowprimes[i]) return true;
|
1121 | return false;
|
1122 | }
|
1123 | if(x.isEven()) return false;
|
1124 | i = 1;
|
1125 | while(i < lowprimes.length) {
|
1126 | var m = lowprimes[i], j = i+1;
|
1127 | while(j < lowprimes.length && m < lplim) m *= lowprimes[j++];
|
1128 | m = x.modInt(m);
|
1129 | while(i < j) if(m%lowprimes[i++] == 0) return false;
|
1130 | }
|
1131 | return x.millerRabin(t);
|
1132 | }
|
1133 |
|
1134 |
|
1135 | function bnpMillerRabin(t) {
|
1136 | var n1 = this.subtract(BigInteger.ONE);
|
1137 | var k = n1.getLowestSetBit();
|
1138 | if(k <= 0) return false;
|
1139 | var r = n1.shiftRight(k);
|
1140 | t = (t+1)>>1;
|
1141 | if(t > lowprimes.length) t = lowprimes.length;
|
1142 | var a = nbi();
|
1143 | for(var i = 0; i < t; ++i) {
|
1144 |
|
1145 | a.fromInt(lowprimes[Math.floor(Math.random()*lowprimes.length)]);
|
1146 | var y = a.modPow(r,this);
|
1147 | if(y.compareTo(BigInteger.ONE) != 0 && y.compareTo(n1) != 0) {
|
1148 | var j = 1;
|
1149 | while(j++ < k && y.compareTo(n1) != 0) {
|
1150 | y = y.modPowInt(2,this);
|
1151 | if(y.compareTo(BigInteger.ONE) == 0) return false;
|
1152 | }
|
1153 | if(y.compareTo(n1) != 0) return false;
|
1154 | }
|
1155 | }
|
1156 | return true;
|
1157 | }
|
1158 |
|
1159 | // protected
|
1160 | BigInteger.prototype.chunkSize = bnpChunkSize;
|
1161 | BigInteger.prototype.toRadix = bnpToRadix;
|
1162 | BigInteger.prototype.fromRadix = bnpFromRadix;
|
1163 | BigInteger.prototype.fromNumber = bnpFromNumber;
|
1164 | BigInteger.prototype.bitwiseTo = bnpBitwiseTo;
|
1165 | BigInteger.prototype.changeBit = bnpChangeBit;
|
1166 | BigInteger.prototype.addTo = bnpAddTo;
|
1167 | BigInteger.prototype.dMultiply = bnpDMultiply;
|
1168 | BigInteger.prototype.dAddOffset = bnpDAddOffset;
|
1169 | BigInteger.prototype.multiplyLowerTo = bnpMultiplyLowerTo;
|
1170 | BigInteger.prototype.multiplyUpperTo = bnpMultiplyUpperTo;
|
1171 | BigInteger.prototype.modInt = bnpModInt;
|
1172 | BigInteger.prototype.millerRabin = bnpMillerRabin;
|
1173 |
|
1174 | // public
|
1175 | BigInteger.prototype.clone = bnClone;
|
1176 | BigInteger.prototype.intValue = bnIntValue;
|
1177 | BigInteger.prototype.byteValue = bnByteValue;
|
1178 | BigInteger.prototype.shortValue = bnShortValue;
|
1179 | BigInteger.prototype.signum = bnSigNum;
|
1180 | BigInteger.prototype.toByteArray = bnToByteArray;
|
1181 | BigInteger.prototype.equals = bnEquals;
|
1182 | BigInteger.prototype.min = bnMin;
|
1183 | BigInteger.prototype.max = bnMax;
|
1184 | BigInteger.prototype.and = bnAnd;
|
1185 | BigInteger.prototype.or = bnOr;
|
1186 | BigInteger.prototype.xor = bnXor;
|
1187 | BigInteger.prototype.andNot = bnAndNot;
|
1188 | BigInteger.prototype.not = bnNot;
|
1189 | BigInteger.prototype.shiftLeft = bnShiftLeft;
|
1190 | BigInteger.prototype.shiftRight = bnShiftRight;
|
1191 | BigInteger.prototype.getLowestSetBit = bnGetLowestSetBit;
|
1192 | BigInteger.prototype.bitCount = bnBitCount;
|
1193 | BigInteger.prototype.testBit = bnTestBit;
|
1194 | BigInteger.prototype.setBit = bnSetBit;
|
1195 | BigInteger.prototype.clearBit = bnClearBit;
|
1196 | BigInteger.prototype.flipBit = bnFlipBit;
|
1197 | BigInteger.prototype.add = bnAdd;
|
1198 | BigInteger.prototype.subtract = bnSubtract;
|
1199 | BigInteger.prototype.multiply = bnMultiply;
|
1200 | BigInteger.prototype.divide = bnDivide;
|
1201 | BigInteger.prototype.remainder = bnRemainder;
|
1202 | BigInteger.prototype.divideAndRemainder = bnDivideAndRemainder;
|
1203 | BigInteger.prototype.modPow = bnModPow;
|
1204 | BigInteger.prototype.modInverse = bnModInverse;
|
1205 | BigInteger.prototype.pow = bnPow;
|
1206 | BigInteger.prototype.gcd = bnGCD;
|
1207 | BigInteger.prototype.isProbablePrime = bnIsProbablePrime;
|
1208 |
|
1209 | // JSBN-specific extension
|
1210 | BigInteger.prototype.square = bnSquare;
|
1211 |
|
1212 | // Expose the Barrett function
|
1213 | BigInteger.prototype.Barrett = Barrett
|
1214 |
|
1215 | // BigInteger interfaces not implemented in jsbn:
|
1216 |
|
1217 | // BigInteger(int signum, byte[] magnitude)
|
1218 | // double doubleValue()
|
1219 | // float floatValue()
|
1220 | // int hashCode()
|
1221 | // long longValue()
|
1222 | // static BigInteger valueOf(long val)
|
1223 |
|
1224 | // Random number generator - requires a PRNG backend, e.g. prng4.js
|
1225 |
|
1226 | // For best results, put code like
|
1227 | // <body onClick='rng_seed_time();' onKeyPress='rng_seed_time();'>
|
1228 | // in your main HTML document.
|
1229 |
|
1230 | var rng_state;
|
1231 | var rng_pool;
|
1232 | var rng_pptr;
|
1233 |
|
1234 | // Mix in a 32-bit integer into the pool
|
1235 | function rng_seed_int(x) {
|
1236 | rng_pool[rng_pptr++] ^= x & 255;
|
1237 | rng_pool[rng_pptr++] ^= (x >> 8) & 255;
|
1238 | rng_pool[rng_pptr++] ^= (x >> 16) & 255;
|
1239 | rng_pool[rng_pptr++] ^= (x >> 24) & 255;
|
1240 | if(rng_pptr >= rng_psize) rng_pptr -= rng_psize;
|
1241 | }
|
1242 |
|
1243 | // Mix in the current time (w/milliseconds) into the pool
|
1244 | function rng_seed_time() {
|
1245 | rng_seed_int(new Date().getTime());
|
1246 | }
|
1247 |
|
1248 | // Initialize the pool with junk if needed.
|
1249 | if(rng_pool == null) {
|
1250 | rng_pool = new Array();
|
1251 | rng_pptr = 0;
|
1252 | var t;
|
1253 | if(typeof window !== "undefined" && window.crypto) {
|
1254 | if (window.crypto.getRandomValues) {
|
1255 | // Use webcrypto if available
|
1256 | var ua = new Uint8Array(32);
|
1257 | window.crypto.getRandomValues(ua);
|
1258 | for(t = 0; t < 32; ++t)
|
1259 | rng_pool[rng_pptr++] = ua[t];
|
1260 | }
|
1261 | else if(navigator.appName == "Netscape" && navigator.appVersion < "5") {
|
1262 | // Extract entropy (256 bits) from NS4 RNG if available
|
1263 | var z = window.crypto.random(32);
|
1264 | for(t = 0; t < z.length; ++t)
|
1265 | rng_pool[rng_pptr++] = z.charCodeAt(t) & 255;
|
1266 | }
|
1267 | }
|
1268 | while(rng_pptr < rng_psize) { // extract some randomness from Math.random()
|
1269 | t = Math.floor(65536 * Math.random());
|
1270 | rng_pool[rng_pptr++] = t >>> 8;
|
1271 | rng_pool[rng_pptr++] = t & 255;
|
1272 | }
|
1273 | rng_pptr = 0;
|
1274 | rng_seed_time();
|
1275 | //rng_seed_int(window.screenX);
|
1276 | //rng_seed_int(window.screenY);
|
1277 | }
|
1278 |
|
1279 | function rng_get_byte() {
|
1280 | if(rng_state == null) {
|
1281 | rng_seed_time();
|
1282 | rng_state = prng_newstate();
|
1283 | rng_state.init(rng_pool);
|
1284 | for(rng_pptr = 0; rng_pptr < rng_pool.length; ++rng_pptr)
|
1285 | rng_pool[rng_pptr] = 0;
|
1286 | rng_pptr = 0;
|
1287 | //rng_pool = null;
|
1288 | }
|
1289 | // TODO: allow reseeding after first request
|
1290 | return rng_state.next();
|
1291 | }
|
1292 |
|
1293 | function rng_get_bytes(ba) {
|
1294 | var i;
|
1295 | for(i = 0; i < ba.length; ++i) ba[i] = rng_get_byte();
|
1296 | }
|
1297 |
|
1298 | function SecureRandom() {}
|
1299 |
|
1300 | SecureRandom.prototype.nextBytes = rng_get_bytes;
|
1301 |
|
1302 | // prng4.js - uses Arcfour as a PRNG
|
1303 |
|
1304 | function Arcfour() {
|
1305 | this.i = 0;
|
1306 | this.j = 0;
|
1307 | this.S = new Array();
|
1308 | }
|
1309 |
|
1310 | // Initialize arcfour context from key, an array of ints, each from [0..255]
|
1311 | function ARC4init(key) {
|
1312 | var i, j, t;
|
1313 | for(i = 0; i < 256; ++i)
|
1314 | this.S[i] = i;
|
1315 | j = 0;
|
1316 | for(i = 0; i < 256; ++i) {
|
1317 | j = (j + this.S[i] + key[i % key.length]) & 255;
|
1318 | t = this.S[i];
|
1319 | this.S[i] = this.S[j];
|
1320 | this.S[j] = t;
|
1321 | }
|
1322 | this.i = 0;
|
1323 | this.j = 0;
|
1324 | }
|
1325 |
|
1326 | function ARC4next() {
|
1327 | var t;
|
1328 | this.i = (this.i + 1) & 255;
|
1329 | this.j = (this.j + this.S[this.i]) & 255;
|
1330 | t = this.S[this.i];
|
1331 | this.S[this.i] = this.S[this.j];
|
1332 | this.S[this.j] = t;
|
1333 | return this.S[(t + this.S[this.i]) & 255];
|
1334 | }
|
1335 |
|
1336 | Arcfour.prototype.init = ARC4init;
|
1337 | Arcfour.prototype.next = ARC4next;
|
1338 |
|
1339 | // Plug in your RNG constructor here
|
1340 | function prng_newstate() {
|
1341 | return new Arcfour();
|
1342 | }
|
1343 |
|
1344 | // Pool size must be a multiple of 4 and greater than 32.
|
1345 | // An array of bytes the size of the pool will be passed to init()
|
1346 | var rng_psize = 256;
|
1347 |
|
1348 | if (typeof exports !== 'undefined') {
|
1349 | exports = module.exports = {
|
1350 | default: BigInteger,
|
1351 | BigInteger: BigInteger,
|
1352 | SecureRandom: SecureRandom,
|
1353 | };
|
1354 | } else {
|
1355 | this.jsbn = {
|
1356 | BigInteger: BigInteger,
|
1357 | SecureRandom: SecureRandom
|
1358 | };
|
1359 | }
|
1360 |
|
1361 | }).call(this);
|