| /* |
| Copyright (c) 2004-2009, The Dojo Foundation All Rights Reserved. |
| Available via Academic Free License >= 2.1 OR the modified BSD license. |
| see: http://dojotoolkit.org/license for details |
| */ |
| |
| |
| if(!dojo._hasResource["dojox.math.BigInteger-ext"]){ |
| dojo._hasResource["dojox.math.BigInteger-ext"]=true; |
| dojo.provide("dojox.math.BigInteger-ext"); |
| dojo.experimental("dojox.math.BigInteger-ext"); |
| dojo.require("dojox.math.BigInteger"); |
| (function(){ |
| var _1=dojox.math.BigInteger,_2=_1._nbi,_3=_1._nbv,_4=_1._nbits,_5=_1._Montgomery; |
| function _6(){ |
| var r=_2(); |
| this._copyTo(r); |
| return r; |
| }; |
| function _7(){ |
| if(this.s<0){ |
| if(this.t==1){ |
| return this[0]-this._DV; |
| }else{ |
| if(this.t==0){ |
| return -1; |
| } |
| } |
| }else{ |
| if(this.t==1){ |
| return this[0]; |
| }else{ |
| if(this.t==0){ |
| return 0; |
| } |
| } |
| } |
| return ((this[1]&((1<<(32-this._DB))-1))<<this._DB)|this[0]; |
| }; |
| function _8(){ |
| return (this.t==0)?this.s:(this[0]<<24)>>24; |
| }; |
| function _9(){ |
| return (this.t==0)?this.s:(this[0]<<16)>>16; |
| }; |
| function _a(r){ |
| return Math.floor(Math.LN2*this._DB/Math.log(r)); |
| }; |
| function _b(){ |
| if(this.s<0){ |
| return -1; |
| }else{ |
| if(this.t<=0||(this.t==1&&this[0]<=0)){ |
| return 0; |
| }else{ |
| return 1; |
| } |
| } |
| }; |
| function _c(b){ |
| if(b==null){ |
| b=10; |
| } |
| if(this.signum()==0||b<2||b>36){ |
| return "0"; |
| } |
| var cs=this._chunkSize(b); |
| var a=Math.pow(b,cs); |
| var d=_3(a),y=_2(),z=_2(),r=""; |
| this._divRemTo(d,y,z); |
| while(y.signum()>0){ |
| r=(a+z.intValue()).toString(b).substr(1)+r; |
| y._divRemTo(d,y,z); |
| } |
| return z.intValue().toString(b)+r; |
| }; |
| function _d(s,b){ |
| this._fromInt(0); |
| if(b==null){ |
| b=10; |
| } |
| var cs=this._chunkSize(b); |
| var d=Math.pow(b,cs),mi=false,j=0,w=0; |
| for(var i=0;i<s.length;++i){ |
| var x=intAt(s,i); |
| if(x<0){ |
| if(s.charAt(i)=="-"&&this.signum()==0){ |
| mi=true; |
| } |
| continue; |
| } |
| w=b*w+x; |
| if(++j>=cs){ |
| this._dMultiply(d); |
| this._dAddOffset(w,0); |
| j=0; |
| w=0; |
| } |
| } |
| if(j>0){ |
| this._dMultiply(Math.pow(b,j)); |
| this._dAddOffset(w,0); |
| } |
| if(mi){ |
| _1.ZERO._subTo(this,this); |
| } |
| }; |
| function _e(a,b,c){ |
| if("number"==typeof b){ |
| if(a<2){ |
| this._fromInt(1); |
| }else{ |
| this._fromNumber(a,c); |
| if(!this.testBit(a-1)){ |
| this._bitwiseTo(_1.ONE.shiftLeft(a-1),_f,this); |
| } |
| if(this._isEven()){ |
| this._dAddOffset(1,0); |
| } |
| while(!this.isProbablePrime(b)){ |
| this._dAddOffset(2,0); |
| if(this.bitLength()>a){ |
| this._subTo(_1.ONE.shiftLeft(a-1),this); |
| } |
| } |
| } |
| }else{ |
| var x=[],t=a&7; |
| x.length=(a>>3)+1; |
| b.nextBytes(x); |
| if(t>0){ |
| x[0]&=((1<<t)-1); |
| }else{ |
| x[0]=0; |
| } |
| this._fromString(x,256); |
| } |
| }; |
| function _10(){ |
| var i=this.t,r=[]; |
| r[0]=this.s; |
| var p=this._DB-(i*this._DB)%8,d,k=0; |
| if(i-->0){ |
| if(p<this._DB&&(d=this[i]>>p)!=(this.s&this._DM)>>p){ |
| r[k++]=d|(this.s<<(this._DB-p)); |
| } |
| while(i>=0){ |
| if(p<8){ |
| d=(this[i]&((1<<p)-1))<<(8-p); |
| d|=this[--i]>>(p+=this._DB-8); |
| }else{ |
| d=(this[i]>>(p-=8))&255; |
| if(p<=0){ |
| p+=this._DB; |
| --i; |
| } |
| } |
| if((d&128)!=0){ |
| d|=-256; |
| } |
| if(k==0&&(this.s&128)!=(d&128)){ |
| ++k; |
| } |
| if(k>0||d!=this.s){ |
| r[k++]=d; |
| } |
| } |
| } |
| return r; |
| }; |
| function _11(a){ |
| return (this.compareTo(a)==0); |
| }; |
| function _12(a){ |
| return (this.compareTo(a)<0)?this:a; |
| }; |
| function _13(a){ |
| return (this.compareTo(a)>0)?this:a; |
| }; |
| function _14(a,op,r){ |
| var i,f,m=Math.min(a.t,this.t); |
| for(i=0;i<m;++i){ |
| r[i]=op(this[i],a[i]); |
| } |
| if(a.t<this.t){ |
| f=a.s&this._DM; |
| for(i=m;i<this.t;++i){ |
| r[i]=op(this[i],f); |
| } |
| r.t=this.t; |
| }else{ |
| f=this.s&this._DM; |
| for(i=m;i<a.t;++i){ |
| r[i]=op(f,a[i]); |
| } |
| r.t=a.t; |
| } |
| r.s=op(this.s,a.s); |
| r._clamp(); |
| }; |
| function _15(x,y){ |
| return x&y; |
| }; |
| function _16(a){ |
| var r=_2(); |
| this._bitwiseTo(a,_15,r); |
| return r; |
| }; |
| function _f(x,y){ |
| return x|y; |
| }; |
| function _17(a){ |
| var r=_2(); |
| this._bitwiseTo(a,_f,r); |
| return r; |
| }; |
| function _18(x,y){ |
| return x^y; |
| }; |
| function _19(a){ |
| var r=_2(); |
| this._bitwiseTo(a,_18,r); |
| return r; |
| }; |
| function _1a(x,y){ |
| return x&~y; |
| }; |
| function _1b(a){ |
| var r=_2(); |
| this._bitwiseTo(a,_1a,r); |
| return r; |
| }; |
| function _1c(){ |
| var r=_2(); |
| for(var i=0;i<this.t;++i){ |
| r[i]=this._DM&~this[i]; |
| } |
| r.t=this.t; |
| r.s=~this.s; |
| return r; |
| }; |
| function _1d(n){ |
| var r=_2(); |
| if(n<0){ |
| this._rShiftTo(-n,r); |
| }else{ |
| this._lShiftTo(n,r); |
| } |
| return r; |
| }; |
| function _1e(n){ |
| var r=_2(); |
| if(n<0){ |
| this._lShiftTo(-n,r); |
| }else{ |
| this._rShiftTo(n,r); |
| } |
| return r; |
| }; |
| function _1f(x){ |
| if(x==0){ |
| return -1; |
| } |
| var r=0; |
| if((x&65535)==0){ |
| x>>=16; |
| r+=16; |
| } |
| if((x&255)==0){ |
| x>>=8; |
| r+=8; |
| } |
| if((x&15)==0){ |
| x>>=4; |
| r+=4; |
| } |
| if((x&3)==0){ |
| x>>=2; |
| r+=2; |
| } |
| if((x&1)==0){ |
| ++r; |
| } |
| return r; |
| }; |
| function _20(){ |
| for(var i=0;i<this.t;++i){ |
| if(this[i]!=0){ |
| return i*this._DB+_1f(this[i]); |
| } |
| } |
| if(this.s<0){ |
| return this.t*this._DB; |
| } |
| return -1; |
| }; |
| function _21(x){ |
| var r=0; |
| while(x!=0){ |
| x&=x-1; |
| ++r; |
| } |
| return r; |
| }; |
| function _22(){ |
| var r=0,x=this.s&this._DM; |
| for(var i=0;i<this.t;++i){ |
| r+=_21(this[i]^x); |
| } |
| return r; |
| }; |
| function _23(n){ |
| var j=Math.floor(n/this._DB); |
| if(j>=this.t){ |
| return (this.s!=0); |
| } |
| return ((this[j]&(1<<(n%this._DB)))!=0); |
| }; |
| function _24(n,op){ |
| var r=_1.ONE.shiftLeft(n); |
| this._bitwiseTo(r,op,r); |
| return r; |
| }; |
| function _25(n){ |
| return this._changeBit(n,_f); |
| }; |
| function _26(n){ |
| return this._changeBit(n,_1a); |
| }; |
| function _27(n){ |
| return this._changeBit(n,_18); |
| }; |
| function _28(a,r){ |
| var i=0,c=0,m=Math.min(a.t,this.t); |
| while(i<m){ |
| c+=this[i]+a[i]; |
| r[i++]=c&this._DM; |
| c>>=this._DB; |
| } |
| if(a.t<this.t){ |
| c+=a.s; |
| while(i<this.t){ |
| c+=this[i]; |
| r[i++]=c&this._DM; |
| c>>=this._DB; |
| } |
| c+=this.s; |
| }else{ |
| c+=this.s; |
| while(i<a.t){ |
| c+=a[i]; |
| r[i++]=c&this._DM; |
| c>>=this._DB; |
| } |
| c+=a.s; |
| } |
| r.s=(c<0)?-1:0; |
| if(c>0){ |
| r[i++]=c; |
| }else{ |
| if(c<-1){ |
| r[i++]=this._DV+c; |
| } |
| } |
| r.t=i; |
| r._clamp(); |
| }; |
| function _29(a){ |
| var r=_2(); |
| this._addTo(a,r); |
| return r; |
| }; |
| function _2a(a){ |
| var r=_2(); |
| this._subTo(a,r); |
| return r; |
| }; |
| function _2b(a){ |
| var r=_2(); |
| this._multiplyTo(a,r); |
| return r; |
| }; |
| function _2c(a){ |
| var r=_2(); |
| this._divRemTo(a,r,null); |
| return r; |
| }; |
| function _2d(a){ |
| var r=_2(); |
| this._divRemTo(a,null,r); |
| return r; |
| }; |
| function _2e(a){ |
| var q=_2(),r=_2(); |
| this._divRemTo(a,q,r); |
| return [q,r]; |
| }; |
| function _2f(n){ |
| this[this.t]=this.am(0,n-1,this,0,0,this.t); |
| ++this.t; |
| this._clamp(); |
| }; |
| function _30(n,w){ |
| while(this.t<=w){ |
| this[this.t++]=0; |
| } |
| this[w]+=n; |
| while(this[w]>=this._DV){ |
| this[w]-=this._DV; |
| if(++w>=this.t){ |
| this[this.t++]=0; |
| } |
| ++this[w]; |
| } |
| }; |
| function _31(){ |
| }; |
| function _32(x){ |
| return x; |
| }; |
| function _33(x,y,r){ |
| x._multiplyTo(y,r); |
| }; |
| function _34(x,r){ |
| x._squareTo(r); |
| }; |
| _31.prototype.convert=_32; |
| _31.prototype.revert=_32; |
| _31.prototype.mulTo=_33; |
| _31.prototype.sqrTo=_34; |
| function _35(e){ |
| return this._exp(e,new _31()); |
| }; |
| function _36(a,n,r){ |
| var i=Math.min(this.t+a.t,n); |
| r.s=0; |
| r.t=i; |
| while(i>0){ |
| r[--i]=0; |
| } |
| var j; |
| for(j=r.t-this.t;i<j;++i){ |
| r[i+this.t]=this.am(0,a[i],r,i,0,this.t); |
| } |
| for(j=Math.min(a.t,n);i<j;++i){ |
| this.am(0,a[i],r,i,0,n-i); |
| } |
| r._clamp(); |
| }; |
| function _37(a,n,r){ |
| --n; |
| var i=r.t=this.t+a.t-n; |
| r.s=0; |
| while(--i>=0){ |
| r[i]=0; |
| } |
| for(i=Math.max(n-this.t,0);i<a.t;++i){ |
| r[this.t+i-n]=this.am(n-i,a[i],r,0,0,this.t+i-n); |
| } |
| r._clamp(); |
| r._drShiftTo(1,r); |
| }; |
| function _38(m){ |
| this.r2=_2(); |
| this.q3=_2(); |
| _1.ONE._dlShiftTo(2*m.t,this.r2); |
| this.mu=this.r2.divide(m); |
| this.m=m; |
| }; |
| function _39(x){ |
| if(x.s<0||x.t>2*this.m.t){ |
| return x.mod(this.m); |
| }else{ |
| if(x.compareTo(this.m)<0){ |
| return x; |
| }else{ |
| var r=_2(); |
| x._copyTo(r); |
| this.reduce(r); |
| return r; |
| } |
| } |
| }; |
| function _3a(x){ |
| return x; |
| }; |
| function _3b(x){ |
| x._drShiftTo(this.m.t-1,this.r2); |
| if(x.t>this.m.t+1){ |
| x.t=this.m.t+1; |
| x._clamp(); |
| } |
| this.mu._multiplyUpperTo(this.r2,this.m.t+1,this.q3); |
| this.m._multiplyLowerTo(this.q3,this.m.t+1,this.r2); |
| while(x.compareTo(this.r2)<0){ |
| x._dAddOffset(1,this.m.t+1); |
| } |
| x._subTo(this.r2,x); |
| while(x.compareTo(this.m)>=0){ |
| x._subTo(this.m,x); |
| } |
| }; |
| function _3c(x,r){ |
| x._squareTo(r); |
| this.reduce(r); |
| }; |
| function _3d(x,y,r){ |
| x._multiplyTo(y,r); |
| this.reduce(r); |
| }; |
| _38.prototype.convert=_39; |
| _38.prototype.revert=_3a; |
| _38.prototype.reduce=_3b; |
| _38.prototype.mulTo=_3d; |
| _38.prototype.sqrTo=_3c; |
| function _3e(e,m){ |
| var i=e.bitLength(),k,r=_3(1),z; |
| if(i<=0){ |
| return r; |
| }else{ |
| if(i<18){ |
| k=1; |
| }else{ |
| if(i<48){ |
| k=3; |
| }else{ |
| if(i<144){ |
| k=4; |
| }else{ |
| if(i<768){ |
| k=5; |
| }else{ |
| k=6; |
| } |
| } |
| } |
| } |
| } |
| if(i<8){ |
| z=new Classic(m); |
| }else{ |
| if(m._isEven()){ |
| z=new _38(m); |
| }else{ |
| z=new _5(m); |
| } |
| } |
| var g=[],n=3,k1=k-1,km=(1<<k)-1; |
| g[1]=z.convert(this); |
| if(k>1){ |
| var g2=_2(); |
| z.sqrTo(g[1],g2); |
| while(n<=km){ |
| g[n]=_2(); |
| z.mulTo(g2,g[n-2],g[n]); |
| n+=2; |
| } |
| } |
| var j=e.t-1,w,is1=true,r2=_2(),t; |
| i=_4(e[j])-1; |
| while(j>=0){ |
| if(i>=k1){ |
| w=(e[j]>>(i-k1))&km; |
| }else{ |
| w=(e[j]&((1<<(i+1))-1))<<(k1-i); |
| if(j>0){ |
| w|=e[j-1]>>(this._DB+i-k1); |
| } |
| } |
| n=k; |
| while((w&1)==0){ |
| w>>=1; |
| --n; |
| } |
| if((i-=n)<0){ |
| i+=this._DB; |
| --j; |
| } |
| if(is1){ |
| g[w]._copyTo(r); |
| is1=false; |
| }else{ |
| while(n>1){ |
| z.sqrTo(r,r2); |
| z.sqrTo(r2,r); |
| n-=2; |
| } |
| if(n>0){ |
| z.sqrTo(r,r2); |
| }else{ |
| t=r; |
| r=r2; |
| r2=t; |
| } |
| z.mulTo(r2,g[w],r); |
| } |
| while(j>=0&&(e[j]&(1<<i))==0){ |
| z.sqrTo(r,r2); |
| t=r; |
| r=r2; |
| r2=t; |
| if(--i<0){ |
| i=this._DB-1; |
| --j; |
| } |
| } |
| } |
| return z.revert(r); |
| }; |
| function _3f(a){ |
| var x=(this.s<0)?this.negate():this.clone(); |
| var y=(a.s<0)?a.negate():a.clone(); |
| if(x.compareTo(y)<0){ |
| var t=x; |
| x=y; |
| y=t; |
| } |
| var i=x.getLowestSetBit(),g=y.getLowestSetBit(); |
| if(g<0){ |
| return x; |
| } |
| if(i<g){ |
| g=i; |
| } |
| if(g>0){ |
| x._rShiftTo(g,x); |
| y._rShiftTo(g,y); |
| } |
| while(x.signum()>0){ |
| if((i=x.getLowestSetBit())>0){ |
| x._rShiftTo(i,x); |
| } |
| if((i=y.getLowestSetBit())>0){ |
| y._rShiftTo(i,y); |
| } |
| if(x.compareTo(y)>=0){ |
| x._subTo(y,x); |
| x._rShiftTo(1,x); |
| }else{ |
| y._subTo(x,y); |
| y._rShiftTo(1,y); |
| } |
| } |
| if(g>0){ |
| y._lShiftTo(g,y); |
| } |
| return y; |
| }; |
| function _40(n){ |
| if(n<=0){ |
| return 0; |
| } |
| var d=this._DV%n,r=(this.s<0)?n-1:0; |
| if(this.t>0){ |
| if(d==0){ |
| r=this[0]%n; |
| }else{ |
| for(var i=this.t-1;i>=0;--i){ |
| r=(d*r+this[i])%n; |
| } |
| } |
| } |
| return r; |
| }; |
| function _41(m){ |
| var ac=m._isEven(); |
| if((this._isEven()&&ac)||m.signum()==0){ |
| return _1.ZERO; |
| } |
| var u=m.clone(),v=this.clone(); |
| var a=_3(1),b=_3(0),c=_3(0),d=_3(1); |
| while(u.signum()!=0){ |
| while(u._isEven()){ |
| u._rShiftTo(1,u); |
| if(ac){ |
| if(!a._isEven()||!b._isEven()){ |
| a._addTo(this,a); |
| b._subTo(m,b); |
| } |
| a._rShiftTo(1,a); |
| }else{ |
| if(!b._isEven()){ |
| b._subTo(m,b); |
| } |
| } |
| b._rShiftTo(1,b); |
| } |
| while(v._isEven()){ |
| v._rShiftTo(1,v); |
| if(ac){ |
| if(!c._isEven()||!d._isEven()){ |
| c._addTo(this,c); |
| d._subTo(m,d); |
| } |
| c._rShiftTo(1,c); |
| }else{ |
| if(!d._isEven()){ |
| d._subTo(m,d); |
| } |
| } |
| d._rShiftTo(1,d); |
| } |
| if(u.compareTo(v)>=0){ |
| u._subTo(v,u); |
| if(ac){ |
| a._subTo(c,a); |
| } |
| b._subTo(d,b); |
| }else{ |
| v._subTo(u,v); |
| if(ac){ |
| c._subTo(a,c); |
| } |
| d._subTo(b,d); |
| } |
| } |
| if(v.compareTo(_1.ONE)!=0){ |
| return _1.ZERO; |
| } |
| if(d.compareTo(m)>=0){ |
| return d.subtract(m); |
| } |
| if(d.signum()<0){ |
| d._addTo(m,d); |
| }else{ |
| return d; |
| } |
| if(d.signum()<0){ |
| return d.add(m); |
| }else{ |
| return d; |
| } |
| }; |
| var _42=[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]; |
| var _43=(1<<26)/_42[_42.length-1]; |
| function _44(t){ |
| var i,x=this.abs(); |
| if(x.t==1&&x[0]<=_42[_42.length-1]){ |
| for(i=0;i<_42.length;++i){ |
| if(x[0]==_42[i]){ |
| return true; |
| } |
| } |
| return false; |
| } |
| if(x._isEven()){ |
| return false; |
| } |
| i=1; |
| while(i<_42.length){ |
| var m=_42[i],j=i+1; |
| while(j<_42.length&&m<_43){ |
| m*=_42[j++]; |
| } |
| m=x._modInt(m); |
| while(i<j){ |
| if(m%_42[i++]==0){ |
| return false; |
| } |
| } |
| } |
| return x._millerRabin(t); |
| }; |
| function _45(t){ |
| var n1=this.subtract(_1.ONE); |
| var k=n1.getLowestSetBit(); |
| if(k<=0){ |
| return false; |
| } |
| var r=n1.shiftRight(k); |
| t=(t+1)>>1; |
| if(t>_42.length){ |
| t=_42.length; |
| } |
| var a=_2(); |
| for(var i=0;i<t;++i){ |
| a._fromInt(_42[i]); |
| var y=a.modPow(r,this); |
| if(y.compareTo(_1.ONE)!=0&&y.compareTo(n1)!=0){ |
| var j=1; |
| while(j++<k&&y.compareTo(n1)!=0){ |
| y=y.modPowInt(2,this); |
| if(y.compareTo(_1.ONE)==0){ |
| return false; |
| } |
| } |
| if(y.compareTo(n1)!=0){ |
| return false; |
| } |
| } |
| } |
| return true; |
| }; |
| dojo.extend(_1,{_chunkSize:_a,_toRadix:_c,_fromRadix:_d,_fromNumber:_e,_bitwiseTo:_14,_changeBit:_24,_addTo:_28,_dMultiply:_2f,_dAddOffset:_30,_multiplyLowerTo:_36,_multiplyUpperTo:_37,_modInt:_40,_millerRabin:_45,clone:_6,intValue:_7,byteValue:_8,shortValue:_9,signum:_b,toByteArray:_10,equals:_11,min:_12,max:_13,and:_16,or:_17,xor:_19,andNot:_1b,not:_1c,shiftLeft:_1d,shiftRight:_1e,getLowestSetBit:_20,bitCount:_22,testBit:_23,setBit:_25,clearBit:_26,flipBit:_27,add:_29,subtract:_2a,multiply:_2b,divide:_2c,remainder:_2d,divideAndRemainder:_2e,modPow:_3e,modInverse:_41,pow:_35,gcd:_3f,isProbablePrime:_44}); |
| })(); |
| } |