index.js 41 KB

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