ebid/web/CrossCert/CC_WSTD_home/jsustoolkit/toolkit/BigInteger.js

(function(){function D(p){function c(a,b){this.value=a;this.sign=b;this.isSmall=!1}function e(a){this.value=a;this.sign=0>a;this.isSmall=!0}function w(a){return-9007199254740992<a&&9007199254740992>a}function v(a){return 1E7>a?[a]:1E14>a?[a%1E7,Math.floor(a/1E7)]:[a%1E7,Math.floor(a/1E7)%1E7,Math.floor(a/1E14)]}function x(a){A(a);var b=a.length;if(4>b&&0>z(a,P))switch(b){case 0:return 0;case 1:return a[0];case 2:return a[0]+1E7*a[1];default:return a[0]+1E7*(a[1]+1E7*a[2])}return a}function A(a){for(var b=
a.length;0===a[--b];);a.length=b+1}function K(a){for(var b=Array(a),d=-1;++d<a;)b[d]=0;return b}function B(a){return 0<a?Math.floor(a):Math.ceil(a)}function C(a,b){var d=a.length,f=b.length,c=Array(d),h=0,e;for(e=0;e<f;e++){var l=a[e]+b[e]+h;h=1E7<=l?1:0;c[e]=l-1E7*h}for(;e<d;)l=a[e]+h,h=1E7===l?1:0,c[e++]=l-1E7*h;0<h&&c.push(h);return c}function E(a,b){return a.length>=b.length?C(a,b):C(b,a)}function L(a,b){var d=a.length,f=Array(d),c;for(c=0;c<d;c++){var e=a[c]-1E7+b;b=Math.floor(e/1E7);f[c]=e-
1E7*b;b+=1}for(;0<b;)f[c++]=b%1E7,b=Math.floor(b/1E7);return f}function F(a,b){var d=a.length,f=b.length,c=Array(d),e=0,g;for(g=0;g<f;g++){var l=a[g]-e-b[g];0>l?(l+=1E7,e=1):e=0;c[g]=l}for(g=f;g<d;g++){l=a[g]-e;if(0>l)l+=1E7;else{c[g++]=l;break}c[g]=l}for(;g<d;g++)c[g]=a[g];A(c);return c}function M(a,b,d){var f=a.length,n=Array(f);b=-b;var h;for(h=0;h<f;h++){var g=a[h]+b;b=Math.floor(g/1E7);g%=1E7;n[h]=0>g?g+1E7:g}n=x(n);return"number"===typeof n?(d&&(n=-n),new e(n)):new c(n,d)}function Q(a,b){var d=
a.length,f=b.length,c=K(d+f),e;for(e=0;e<d;++e){var g=a[e];for(var l=0;l<f;++l){var k=b[l];k=g*k+c[e+l];var m=Math.floor(k/1E7);c[e+l]=k-1E7*m;c[e+l+1]+=m}}A(c);return c}function G(a,b){var d=a.length,f=Array(d),c=0,e;for(e=0;e<d;e++){var g=a[e]*b+c;c=Math.floor(g/1E7);f[e]=g-1E7*c}for(;0<c;)f[e++]=c%1E7,c=Math.floor(c/1E7);return f}function D(a,b){for(var d=[];0<b--;)d.push(0);return d.concat(a)}function N(a,b){var d=Math.max(a.length,b.length);if(400>=d)return Q(a,b);d=Math.ceil(d/2);var f=a.slice(d);
a=a.slice(0,d);var c=b.slice(d),e=b.slice(0,d);b=N(a,e);var g=N(f,c);f=N(E(a,f),E(e,c));d=E(E(b,D(F(F(f,b),g),d)),D(g,2*d));A(d);return d}function J(a,b,d){return 1E7>a?new c(G(b,a),d):new c(Q(b,v(a)),d)}function S(a){var b=a.length,d=K(b+b),f;for(f=0;f<b;f++){var c=a[f];for(var e=0;e<b;e++){var g=a[e];g=c*g+d[f+e];var l=Math.floor(g/1E7);d[f+e]=g-1E7*l;d[f+e+1]+=l}}A(d);return d}function T(a,b){var d=a.length,f=K(d);var c=0;for(--d;0<=d;--d){c=1E7*c+a[d];var e=B(c/b);c-=e*b;f[d]=e|0}return[f,c|0]}
function H(a,b){b=m(b);var d=a.value;var f=b.value;if(0===f)throw Error("Cannot divide by zero");if(a.isSmall)return b.isSmall?[new e(B(d/f)),new e(d%f)]:[k[0],a];if(b.isSmall){if(1===f)return[a,k[0]];if(-1==f)return[a.negate(),k[0]];f=Math.abs(f);if(1E7>f)return f=T(d,f),d=x(f[0]),f=f[1],a.sign&&(f=-f),"number"===typeof d?(a.sign!==b.sign&&(d=-d),[new e(d),new e(f)]):[new c(d,a.sign!==b.sign),new e(f)];f=v(f)}var n=z(d,f);if(-1===n)return[k[0],a];if(0===n)return[k[a.sign===b.sign?1:-1],k[0]];if(200>=
d.length+f.length){var h=f,g=d.length;f=h.length;n=K(h.length);var l=h[f-1],y=Math.ceil(1E7/(2*l));d=G(d,y);h=G(h,y);var q,r,t;d.length<=g&&d.push(0);h.push(0);l=h[f-1];for(q=g-f;0<=q;q--){g=9999999;d[q+f]!==l&&(g=Math.floor((1E7*d[q+f]+d[q+f-1])/l));var p=r=0;var w=h.length;for(t=0;t<w;t++){r+=g*h[t];var u=Math.floor(r/1E7);p+=d[q+t]-(r-1E7*u);r=u;0>p?(d[q+t]=p+1E7,p=-1):(d[q+t]=p,p=0)}for(;0!==p;){--g;for(t=r=0;t<w;t++)r+=d[q+t]-1E7+h[t],0>r?(d[q+t]=r+1E7,r=0):(d[q+t]=r,r=1);p+=r}n[q]=g}d=T(d,y)[0];
f=[x(n),x(d)]}else{n=d.length;l=f.length;y=[];for(h=[];n;)if(h.unshift(d[--n]),0>z(h,f))y.push(0);else{g=h.length;q=1E7*h[g-1]+h[g-2];r=1E7*f[l-1]+f[l-2];g>l&&(q=1E7*(q+1));g=Math.ceil(q/r);do{q=G(f,g);if(0>=z(q,h))break;g--}while(g);y.push(g);h=F(h,q)}y.reverse();f=[x(y),x(h)]}d=f[0];b=a.sign!==b.sign;f=f[1];a=a.sign;"number"===typeof d?(b&&(d=-d),d=new e(d)):d=new c(d,b);"number"===typeof f?(a&&(f=-f),f=new e(f)):f=new c(f,a);return[d,f]}function z(a,b){if(a.length!==b.length)return a.length>b.length?
1:-1;for(var d=a.length-1;0<=d;d--)if(a[d]!==b[d])return a[d]>b[d]?1:-1;return 0}function U(a){a=a.abs();if(a.isUnit())return!1;if(a.equals(2)||a.equals(3)||a.equals(5))return!0;if(a.isEven()||a.isDivisibleBy(3)||a.isDivisibleBy(5))return!1;if(a.lesser(25))return!0}function V(a){return("number"===typeof a||"string"===typeof a)&&1E7>=+Math.abs(a)||a instanceof c&&1>=a.value.length}function R(a,b,d){b=m(b);var c=a.isNegative(),e=b.isNegative(),h=c?a.not():a,g=e?b.not():b;b=[];a=[];for(var l=!1,k=!1;!l||
!k;)h.isZero()?(l=!0,b.push(c?1:0)):c?b.push(h.isEven()?1:0):b.push(h.isEven()?0:1),g.isZero()?(k=!0,a.push(e?1:0)):e?a.push(g.isEven()?1:0):a.push(g.isEven()?0:1),h=h.over(2),g=g.over(2);c=[];for(e=0;e<b.length;e++)c.push(d(b[e],a[e]));for(d=bigInt(c.pop()).negate().times(bigInt(2).pow(c.length));c.length;)d=d.add(bigInt(c.pop()).times(bigInt(2).pow(c.length)));return d}function O(a){a=a.value;a="number"===typeof a?a|1073741824:a[0]+1E7*a[1]|1073758208;return a&-a}function W(a,b){a=m(a);b=m(b);return a.greater(b)?
a:b}function X(a,b){a=m(a);b=m(b);return a.lesser(b)?a:b}function Y(a,b){a=m(a).abs();b=m(b).abs();if(a.equals(b))return a;if(a.isZero())return b;if(b.isZero())return a;for(var d=k[1],c;a.isEven()&&b.isEven();)c=Math.min(O(a),O(b)),a=a.divide(c),b=b.divide(c),d=d.multiply(c);for(;a.isEven();)a=a.divide(O(a));do{for(;b.isEven();)b=b.divide(O(b));a.greater(b)&&(c=b,b=a,a=c);b=b.subtract(a)}while(!b.isZero());return d.isUnit()?a:a.multiply(d)}function Z(a){a=a.value;"number"===typeof a&&(a=[a]);return 1===
a.length&&35>=a[0]?"0123456789abcdefghijklmnopqrstuvwxyz".charAt(a[0]):"<"+a+">"}function aa(a,b){b=bigInt(b);if(b.isZero()){if(a.isZero())return"0";throw Error("Cannot convert nonzero numbers to base 0.");}if(b.equals(-1))return a.isZero()?"0":a.isNegative()?Array(1-a).join("10"):"1"+Array(+a).join("01");var d="";a.isNegative()&&b.isPositive()&&(d="-",a=a.abs());if(b.equals(1))return a.isZero()?"0":d+Array(+a+1).join(1);for(var c=[],e;a.isNegative()||0<=a.compareAbs(b);)e=a.divmod(b),a=e.quotient,
e=e.remainder,e.isNegative()&&(e=b.minus(e).abs(),a=a.next()),c.push(Z(e));c.push(Z(a));return d+c.reverse().join("")}function ba(a){if(w(+a)){var b=+a;if(b===B(b))return new e(b);throw"Invalid integer: "+a;}(b="-"===a[0])&&(a=a.slice(1));var d=a.split(/e/i);if(2<d.length)throw Error("Invalid integer: "+f.join("e"));if(2===d.length){a=d[1];"+"===a[0]&&(a=a.slice(1));a=+a;if(a!==B(a)||!w(a))throw Error("Invalid integer: "+a+" is not a valid exponent.");var f=d[0];d=f.indexOf(".");0<=d&&(a-=f.length-
d-1,f=f.slice(0,d)+f.slice(d+1));if(0>a)throw Error("Cannot include negative exponent part for integers");a=f+=Array(a+1).join("0")}if(!/^([0-9][0-9]*)$/.test(a))throw Error("Invalid integer: "+a);f=[];d=a.length;for(var k=d-7;0<d;)f.push(+a.slice(k,d)),k-=7,0>k&&(k=0),d-=7;A(f);return new c(f,b)}function m(a){return"number"===typeof a?(a=w(a)?new e(a):ba(a.toString()),a):"string"===typeof a?ba(a):a}var P=v(9007199254740992),da=Math.log(9007199254740992);c.prototype.add=function(a){a=m(a);if(this.sign!==
a.sign)return this.subtract(a.negate());var b=this.value,d=a.value;return a.isSmall?new c(L(b,Math.abs(d)),this.sign):new c(E(b,d),this.sign)};c.prototype.plus=c.prototype.add;e.prototype.add=function(a){a=m(a);var b=this.value;if(0>b!==a.sign)return this.subtract(a.negate());var d=a.value;if(a.isSmall){if(w(b+d))return new e(b+d);d=v(Math.abs(d))}return new c(L(d,Math.abs(b)),0>b)};e.prototype.plus=e.prototype.add;c.prototype.subtract=function(a){var b=m(a);if(this.sign!==b.sign)return this.add(b.negate());
a=this.value;var d=b.value;if(b.isSmall)return M(a,Math.abs(d),this.sign);b=this.sign;0<=z(a,d)?a=F(a,d):(a=F(d,a),b=!b);a=x(a);"number"===typeof a?(b&&(a=-a),a=new e(a)):a=new c(a,b);return a};c.prototype.minus=c.prototype.subtract;e.prototype.subtract=function(a){a=m(a);var b=this.value;if(0>b!==a.sign)return this.add(a.negate());var d=a.value;return a.isSmall?new e(b-d):M(d,Math.abs(b),0<=b)};e.prototype.minus=e.prototype.subtract;c.prototype.negate=function(){return new c(this.value,!this.sign)};
e.prototype.negate=function(){var a=this.sign,b=new e(-this.value);b.sign=!a;return b};c.prototype.abs=function(){return new c(this.value,!1)};e.prototype.abs=function(){return new e(Math.abs(this.value))};c.prototype.multiply=function(a){var b=m(a);a=this.value;var d=b.value,e=this.sign!==b.sign;if(b.isSmall){if(0===d)return k[0];if(1===d)return this;if(-1===d)return this.negate();b=Math.abs(d);if(1E7>b)return new c(G(a,b),e);d=v(b)}return 4E3<a.length+d.length?new c(N(a,d),e):new c(Q(a,d),e)};c.prototype.times=
c.prototype.multiply;e.prototype._multiplyBySmall=function(a){return w(a.value*this.value)?new e(a.value*this.value):J(Math.abs(a.value),v(Math.abs(this.value)),this.sign!==a.sign)};c.prototype._multiplyBySmall=function(a){return 0===a.value?k[0]:1===a.value?this:-1===a.value?this.negate():J(Math.abs(a.value),this.value,this.sign!==a.sign)};e.prototype.multiply=function(a){return m(a)._multiplyBySmall(this)};e.prototype.times=e.prototype.multiply;c.prototype.square=function(){return new c(S(this.value),
!1)};e.prototype.square=function(){var a=this.value*this.value;return w(a)?new e(a):new c(S(v(Math.abs(this.value))),!1)};c.prototype.divmod=function(a){a=H(this,a);return{quotient:a[0],remainder:a[1]}};e.prototype.divmod=c.prototype.divmod;c.prototype.divide=function(a){return H(this,a)[0]};e.prototype.over=e.prototype.divide=c.prototype.over=c.prototype.divide;c.prototype.mod=function(a){return H(this,a)[1]};e.prototype.remainder=e.prototype.mod=c.prototype.remainder=c.prototype.mod;c.prototype.pow=
function(a){var b=m(a),d=this.value;a=b.value;var c;if(0===a)return k[1];if(0===d)return k[0];if(1===d)return k[1];if(-1===d)return b.isEven()?k[1]:k[-1];if(b.sign)return k[0];if(!b.isSmall)throw Error("The exponent "+b.toString()+" is too large.");if(this.isSmall&&w(c=Math.pow(d,a)))return new e(B(c));c=this;for(b=k[1];;){a&1&&(b=b.times(c),--a);if(0===a)break;a/=2;c=c.square()}return b};e.prototype.pow=c.prototype.pow;c.prototype.modPow=function(a,b){a=m(a);b=m(b);if(b.isZero())throw Error("Cannot take modPow with modulus 0");
for(var d=k[1],c=this.mod(b);a.isPositive();){if(c.isZero())return k[0];a.isOdd()&&(d=d.multiply(c).mod(b));a=a.divide(2);c=c.square().mod(b)}return d};e.prototype.modPow=c.prototype.modPow;c.prototype.compareAbs=function(a){a=m(a);return a.isSmall?1:z(this.value,a.value)};e.prototype.compareAbs=function(a){a=m(a);var b=Math.abs(this.value),d=a.value;return a.isSmall?(d=Math.abs(d),b===d?0:b>d?1:-1):-1};c.prototype.compare=function(a){if(Infinity===a)return-1;if(-Infinity===a)return 1;a=m(a);return this.sign!==
a.sign?a.sign?1:-1:a.isSmall?this.sign?-1:1:z(this.value,a.value)*(this.sign?-1:1)};c.prototype.compareTo=c.prototype.compare;e.prototype.compare=function(a){if(Infinity===a)return-1;if(-Infinity===a)return 1;a=m(a);var b=this.value,d=a.value;return a.isSmall?b==d?0:b>d?1:-1:0>b!==a.sign?0>b?-1:1:0>b?1:-1};e.prototype.compareTo=e.prototype.compare;c.prototype.equals=function(a){return 0===this.compare(a)};e.prototype.eq=e.prototype.equals=c.prototype.eq=c.prototype.equals;c.prototype.notEquals=function(a){return 0!==
this.compare(a)};e.prototype.neq=e.prototype.notEquals=c.prototype.neq=c.prototype.notEquals;c.prototype.greater=function(a){return 0<this.compare(a)};e.prototype.gt=e.prototype.greater=c.prototype.gt=c.prototype.greater;c.prototype.lesser=function(a){return 0>this.compare(a)};e.prototype.lt=e.prototype.lesser=c.prototype.lt=c.prototype.lesser;c.prototype.greaterOrEquals=function(a){return 0<=this.compare(a)};e.prototype.geq=e.prototype.greaterOrEquals=c.prototype.geq=c.prototype.greaterOrEquals;
c.prototype.lesserOrEquals=function(a){return 0>=this.compare(a)};e.prototype.leq=e.prototype.lesserOrEquals=c.prototype.leq=c.prototype.lesserOrEquals;c.prototype.isEven=function(){return 0===(this.value[0]&1)};e.prototype.isEven=function(){return 0===(this.value&1)};c.prototype.isOdd=function(){return 1===(this.value[0]&1)};e.prototype.isOdd=function(){return 1===(this.value&1)};c.prototype.isPositive=function(){return!this.sign};e.prototype.isPositive=function(){return 0<this.value};c.prototype.isNegative=
function(){return this.sign};e.prototype.isNegative=function(){return 0>this.value};c.prototype.isUnit=function(){return!1};e.prototype.isUnit=function(){return 1===Math.abs(this.value)};c.prototype.isZero=function(){return!1};e.prototype.isZero=function(){return 0===this.value};c.prototype.isDivisibleBy=function(a){a=m(a);var b=a.value;return 0===b?!1:1===b?!0:2===b?this.isEven():this.mod(a).equals(k[0])};e.prototype.isDivisibleBy=c.prototype.isDivisibleBy;c.prototype.isPrime=function(){var a=U(this);
if(void 0!==a)return a;a=this.abs();for(var b=a.prev(),d=[2,3,5,7,11,13,17,19],c=b,e,h,g,l;c.isEven();)c=c.divide(2);for(g=0;g<d.length;g++)if(l=bigInt(d[g]).modPow(c,a),!l.equals(k[1])&&!l.equals(b)){h=!0;for(e=c;h&&e.lesser(b);e=e.multiply(2))l=l.square().mod(a),l.equals(b)&&(h=!1);if(h)return!1}return!0};e.prototype.isPrime=c.prototype.isPrime;c.prototype.isProbablePrime=function(a){var b=U(this);if(void 0!==b)return b;b=this.abs();a=void 0===a?5:a;for(var d=0;d<a;d++)if(!bigInt.randBetween(2,
b.minus(2)).modPow(b.prev(),b).isUnit())return!1;return!0};e.prototype.isProbablePrime=c.prototype.isProbablePrime;c.prototype.next=function(){var a=this.value;return this.sign?M(a,1,this.sign):new c(L(a,1),this.sign)};e.prototype.next=function(){var a=this.value;return 9007199254740992>a+1?new e(a+1):new c(P,!1)};c.prototype.prev=function(){var a=this.value;return this.sign?new c(L(a,1),!0):M(a,1,this.sign)};e.prototype.prev=function(){var a=this.value;return-9007199254740992<a-1?new e(a-1):new c(P,
!0)};for(var u=[1];1E7>=u[u.length-1];)u.push(2*u[u.length-1]);var I=u.length,ca=u[I-1];c.prototype.shiftLeft=function(a){if(!V(a))throw Error(String(a)+" is too large for shifting.");a=+a;if(0>a)return this.shiftRight(-a);for(var b=this;a>=I;)b=b.multiply(ca),a-=I-1;return b.multiply(u[a])};e.prototype.shiftLeft=c.prototype.shiftLeft;c.prototype.shiftRight=function(a){var b;if(!V(a))throw Error(String(a)+" is too large for shifting.");a=+a;if(0>a)return this.shiftLeft(-a);for(b=this;a>=I;){if(b.isZero())return b;
b=H(b,ca);b=b[1].isNegative()?b[0].prev():b[0];a-=I-1}b=H(b,u[a]);return b[1].isNegative()?b[0].prev():b[0]};e.prototype.shiftRight=c.prototype.shiftRight;c.prototype.not=function(){return this.negate().prev()};e.prototype.not=c.prototype.not;c.prototype.and=function(a){return R(this,a,function(a,d){return a&d})};e.prototype.and=c.prototype.and;c.prototype.or=function(a){return R(this,a,function(a,d){return a|d})};e.prototype.or=c.prototype.or;c.prototype.xor=function(a){return R(this,a,function(a,
d){return a^d})};e.prototype.xor=c.prototype.xor;c.prototype.toString=function(a){void 0===a&&(a=10);if(10!==a)return aa(this,a);a=this.value;for(var b=a.length,d=String(a[--b]),c;0<=--b;)c=String(a[b]),d+="0000000".slice(c.length)+c;return(this.sign?"-":"")+d};e.prototype.toString=function(a){void 0===a&&(a=10);return 10!=a?aa(this,a):String(this.value)};c.prototype.valueOf=function(){return+this.toString()};c.prototype.toJSNumber=c.prototype.valueOf;e.prototype.valueOf=function(){return this.value};
e.prototype.toJSNumber=e.prototype.valueOf;var k=function(a,b){if("undefined"===typeof a)return k[0];if("undefined"!==typeof b){if(10===+b)a=m(a);else{var d=k[0],c=k[1],n=a.length;if(2<=b&&36>=b&&n<=da/Math.log(b))a=new e(parseInt(a,b));else{b=m(b);n=[];var h,g="-"===a[0];for(h=g?1:0;h<a.length;h++){var l=a[h].toLowerCase(),p=l.charCodeAt(0);if(48<=p&&57>=p)n.push(m(l));else if(97<=p&&122>=p)n.push(m(l.charCodeAt(0)-87));else if("<"===l){l=h;do h++;while(">"!==a[h]);n.push(m(a.slice(l+1,h)))}else throw Error(l+
" is not a valid character");}n.reverse();for(h=0;h<n.length;h++)d=d.add(n[h].times(c)),c=c.times(b);a=g?d.negate():d}}return a}return m(a)};for(p=0;1E3>p;p++)k[p]=new e(p),0<p&&(k[-p]=new e(-p));k.one=k[1];k.zero=k[0];k.minusOne=k[-1];k.max=W;k.min=X;k.gcd=Y;k.lcm=function(a,b){a=m(a).abs();b=m(b).abs();return a.divide(Y(a,b)).multiply(b)};k.isInstance=function(a){return a instanceof c||a instanceof e};k.randBetween=function(a,b){a=m(a);b=m(b);var d=X(a,b);a=W(a,b).subtract(d);if(a.isSmall)return d.add(Math.round(Math.random()*
a));b=[];for(var f=!0,k=a.value.length-1;0<=k;k--){var h=f?a.value[k]:1E7,g=B(Math.random()*h);b.unshift(g);g<h&&(f=!1)}b=x(b);return d.add("number"===typeof b?new e(b):new c(b,!1))};return k}var J=[],C=null;"function"!==typeof define&&("object"===typeof module&&module.exports?C=function(p,c){c(require,module)}:(crosscert=window.crosscert=window.crosscert||{},D(crosscert)));(C||"function"===typeof define)&&(C||define)(["require","module"].concat(J),function(p,c){c.exports=function(c){var e=J.map(function(c){return p(c)}).concat(D);
c=c||{};c.defined=c.defined||{};if(c.defined.jsbn)return c.jsbn;c.defined.jsbn=!0;for(var v=0;v<e.length;++v)e[v](c);return c.jsbn}})})();