root / trunk / web / dojo / dojox / math / BigInteger-ext.js @ 10
History | View | Annotate | Download (11.8 KB)
| 1 | 9 | andrej.cim | /*
|
|---|---|---|---|
| 2 | Copyright (c) 2004-2010, The Dojo Foundation All Rights Reserved.
|
||
| 3 | Available via Academic Free License >= 2.1 OR the modified BSD license.
|
||
| 4 | see: http://dojotoolkit.org/license for details
|
||
| 5 | */
|
||
| 6 | |||
| 7 | |||
| 8 | if(!dojo._hasResource["dojox.math.BigInteger-ext"]){ |
||
| 9 | dojo._hasResource["dojox.math.BigInteger-ext"]=true; |
||
| 10 | dojo.provide("dojox.math.BigInteger-ext");
|
||
| 11 | dojo.experimental("dojox.math.BigInteger-ext");
|
||
| 12 | dojo.require("dojox.math.BigInteger");
|
||
| 13 | (function(){
|
||
| 14 | var _1=dojox.math.BigInteger,_2=_1._nbi,_3=_1._nbv,_4=_1._nbits,_5=_1._Montgomery;
|
||
| 15 | function _6(){ |
||
| 16 | var r=_2();
|
||
| 17 | this._copyTo(r);
|
||
| 18 | return r;
|
||
| 19 | }; |
||
| 20 | function _7(){ |
||
| 21 | if(this.s<0){ |
||
| 22 | if(this.t==1){ |
||
| 23 | return this[0]-this._DV; |
||
| 24 | }else{
|
||
| 25 | if(this.t==0){ |
||
| 26 | return -1; |
||
| 27 | } |
||
| 28 | } |
||
| 29 | }else{
|
||
| 30 | if(this.t==1){ |
||
| 31 | return this[0]; |
||
| 32 | }else{
|
||
| 33 | if(this.t==0){ |
||
| 34 | return 0; |
||
| 35 | } |
||
| 36 | } |
||
| 37 | } |
||
| 38 | return ((this[1]&((1<<(32-this._DB))-1))<<this._DB)|this[0]; |
||
| 39 | }; |
||
| 40 | function _8(){ |
||
| 41 | return (this.t==0)?this.s:(this[0]<<24)>>24; |
||
| 42 | }; |
||
| 43 | function _9(){ |
||
| 44 | return (this.t==0)?this.s:(this[0]<<16)>>16; |
||
| 45 | }; |
||
| 46 | function _a(r){ |
||
| 47 | return Math.floor(Math.LN2*this._DB/Math.log(r)); |
||
| 48 | }; |
||
| 49 | function _b(){ |
||
| 50 | if(this.s<0){ |
||
| 51 | return -1; |
||
| 52 | }else{
|
||
| 53 | if(this.t<=0||(this.t==1&&this[0]<=0)){ |
||
| 54 | return 0; |
||
| 55 | }else{
|
||
| 56 | return 1; |
||
| 57 | } |
||
| 58 | } |
||
| 59 | }; |
||
| 60 | function _c(b){ |
||
| 61 | if(b==null){ |
||
| 62 | b=10;
|
||
| 63 | } |
||
| 64 | if(this.signum()==0||b<2||b>36){ |
||
| 65 | return "0"; |
||
| 66 | } |
||
| 67 | var cs=this._chunkSize(b); |
||
| 68 | var a=Math.pow(b,cs);
|
||
| 69 | var d=_3(a),y=_2(),z=_2(),r=""; |
||
| 70 | this._divRemTo(d,y,z);
|
||
| 71 | while(y.signum()>0){ |
||
| 72 | r=(a+z.intValue()).toString(b).substr(1)+r;
|
||
| 73 | y._divRemTo(d,y,z); |
||
| 74 | } |
||
| 75 | return z.intValue().toString(b)+r;
|
||
| 76 | }; |
||
| 77 | function _d(s,b){ |
||
| 78 | this._fromInt(0); |
||
| 79 | if(b==null){ |
||
| 80 | b=10;
|
||
| 81 | } |
||
| 82 | var cs=this._chunkSize(b); |
||
| 83 | var d=Math.pow(b,cs),mi=false,j=0,w=0; |
||
| 84 | for(var i=0;i<s.length;++i){ |
||
| 85 | var x=intAt(s,i);
|
||
| 86 | if(x<0){ |
||
| 87 | if(s.charAt(i)=="-"&&this.signum()==0){ |
||
| 88 | mi=true;
|
||
| 89 | } |
||
| 90 | continue;
|
||
| 91 | } |
||
| 92 | w=b*w+x; |
||
| 93 | if(++j>=cs){
|
||
| 94 | this._dMultiply(d);
|
||
| 95 | this._dAddOffset(w,0); |
||
| 96 | j=0;
|
||
| 97 | w=0;
|
||
| 98 | } |
||
| 99 | } |
||
| 100 | if(j>0){ |
||
| 101 | this._dMultiply(Math.pow(b,j));
|
||
| 102 | this._dAddOffset(w,0); |
||
| 103 | } |
||
| 104 | if(mi){
|
||
| 105 | _1.ZERO._subTo(this,this); |
||
| 106 | } |
||
| 107 | }; |
||
| 108 | function _e(a,b,c){ |
||
| 109 | if("number"==typeof b){ |
||
| 110 | if(a<2){ |
||
| 111 | this._fromInt(1); |
||
| 112 | }else{
|
||
| 113 | this._fromNumber(a,c);
|
||
| 114 | if(!this.testBit(a-1)){ |
||
| 115 | this._bitwiseTo(_1.ONE.shiftLeft(a-1),_f,this); |
||
| 116 | } |
||
| 117 | if(this._isEven()){ |
||
| 118 | this._dAddOffset(1,0); |
||
| 119 | } |
||
| 120 | while(!this.isProbablePrime(b)){ |
||
| 121 | this._dAddOffset(2,0); |
||
| 122 | if(this.bitLength()>a){ |
||
| 123 | this._subTo(_1.ONE.shiftLeft(a-1),this); |
||
| 124 | } |
||
| 125 | } |
||
| 126 | } |
||
| 127 | }else{
|
||
| 128 | var x=[],t=a&7; |
||
| 129 | x.length=(a>>3)+1; |
||
| 130 | b.nextBytes(x); |
||
| 131 | if(t>0){ |
||
| 132 | x[0]&=((1<<t)-1); |
||
| 133 | }else{
|
||
| 134 | x[0]=0; |
||
| 135 | } |
||
| 136 | this._fromString(x,256); |
||
| 137 | } |
||
| 138 | }; |
||
| 139 | function _10(){ |
||
| 140 | var i=this.t,r=[]; |
||
| 141 | r[0]=this.s; |
||
| 142 | var p=this._DB-(i*this._DB)%8,d,k=0; |
||
| 143 | if(i-->0){ |
||
| 144 | if(p<this._DB&&(d=this[i]>>p)!=(this.s&this._DM)>>p){ |
||
| 145 | r[k++]=d|(this.s<<(this._DB-p)); |
||
| 146 | } |
||
| 147 | while(i>=0){ |
||
| 148 | if(p<8){ |
||
| 149 | d=(this[i]&((1<<p)-1))<<(8-p); |
||
| 150 | d|=this[--i]>>(p+=this._DB-8); |
||
| 151 | }else{
|
||
| 152 | d=(this[i]>>(p-=8))&255; |
||
| 153 | if(p<=0){ |
||
| 154 | p+=this._DB;
|
||
| 155 | --i; |
||
| 156 | } |
||
| 157 | } |
||
| 158 | if((d&128)!=0){ |
||
| 159 | d|=-256;
|
||
| 160 | } |
||
| 161 | if(k==0&&(this.s&128)!=(d&128)){ |
||
| 162 | ++k; |
||
| 163 | } |
||
| 164 | if(k>0||d!=this.s){ |
||
| 165 | r[k++]=d; |
||
| 166 | } |
||
| 167 | } |
||
| 168 | } |
||
| 169 | return r;
|
||
| 170 | }; |
||
| 171 | function _11(a){ |
||
| 172 | return (this.compareTo(a)==0); |
||
| 173 | }; |
||
| 174 | function _12(a){ |
||
| 175 | return (this.compareTo(a)<0)?this:a; |
||
| 176 | }; |
||
| 177 | function _13(a){ |
||
| 178 | return (this.compareTo(a)>0)?this:a; |
||
| 179 | }; |
||
| 180 | function _14(a,op,r){ |
||
| 181 | var i,f,m=Math.min(a.t,this.t); |
||
| 182 | for(i=0;i<m;++i){ |
||
| 183 | r[i]=op(this[i],a[i]);
|
||
| 184 | } |
||
| 185 | if(a.t<this.t){ |
||
| 186 | f=a.s&this._DM;
|
||
| 187 | for(i=m;i<this.t;++i){ |
||
| 188 | r[i]=op(this[i],f);
|
||
| 189 | } |
||
| 190 | r.t=this.t;
|
||
| 191 | }else{
|
||
| 192 | f=this.s&this._DM; |
||
| 193 | for(i=m;i<a.t;++i){
|
||
| 194 | r[i]=op(f,a[i]); |
||
| 195 | } |
||
| 196 | r.t=a.t; |
||
| 197 | } |
||
| 198 | r.s=op(this.s,a.s);
|
||
| 199 | r._clamp(); |
||
| 200 | }; |
||
| 201 | function _15(x,y){ |
||
| 202 | return x&y;
|
||
| 203 | }; |
||
| 204 | function _16(a){ |
||
| 205 | var r=_2();
|
||
| 206 | this._bitwiseTo(a,_15,r);
|
||
| 207 | return r;
|
||
| 208 | }; |
||
| 209 | function _f(x,y){ |
||
| 210 | return x|y;
|
||
| 211 | }; |
||
| 212 | function _17(a){ |
||
| 213 | var r=_2();
|
||
| 214 | this._bitwiseTo(a,_f,r);
|
||
| 215 | return r;
|
||
| 216 | }; |
||
| 217 | function _18(x,y){ |
||
| 218 | return x^y;
|
||
| 219 | }; |
||
| 220 | function _19(a){ |
||
| 221 | var r=_2();
|
||
| 222 | this._bitwiseTo(a,_18,r);
|
||
| 223 | return r;
|
||
| 224 | }; |
||
| 225 | function _1a(x,y){ |
||
| 226 | return x&~y;
|
||
| 227 | }; |
||
| 228 | function _1b(a){ |
||
| 229 | var r=_2();
|
||
| 230 | this._bitwiseTo(a,_1a,r);
|
||
| 231 | return r;
|
||
| 232 | }; |
||
| 233 | function _1c(){ |
||
| 234 | var r=_2();
|
||
| 235 | for(var i=0;i<this.t;++i){ |
||
| 236 | r[i]=this._DM&~this[i]; |
||
| 237 | } |
||
| 238 | r.t=this.t;
|
||
| 239 | r.s=~this.s;
|
||
| 240 | return r;
|
||
| 241 | }; |
||
| 242 | function _1d(n){ |
||
| 243 | var r=_2();
|
||
| 244 | if(n<0){ |
||
| 245 | this._rShiftTo(-n,r);
|
||
| 246 | }else{
|
||
| 247 | this._lShiftTo(n,r);
|
||
| 248 | } |
||
| 249 | return r;
|
||
| 250 | }; |
||
| 251 | function _1e(n){ |
||
| 252 | var r=_2();
|
||
| 253 | if(n<0){ |
||
| 254 | this._lShiftTo(-n,r);
|
||
| 255 | }else{
|
||
| 256 | this._rShiftTo(n,r);
|
||
| 257 | } |
||
| 258 | return r;
|
||
| 259 | }; |
||
| 260 | function _1f(x){ |
||
| 261 | if(x==0){ |
||
| 262 | return -1; |
||
| 263 | } |
||
| 264 | var r=0; |
||
| 265 | if((x&65535)==0){ |
||
| 266 | x>>=16;
|
||
| 267 | r+=16;
|
||
| 268 | } |
||
| 269 | if((x&255)==0){ |
||
| 270 | x>>=8;
|
||
| 271 | r+=8;
|
||
| 272 | } |
||
| 273 | if((x&15)==0){ |
||
| 274 | x>>=4;
|
||
| 275 | r+=4;
|
||
| 276 | } |
||
| 277 | if((x&3)==0){ |
||
| 278 | x>>=2;
|
||
| 279 | r+=2;
|
||
| 280 | } |
||
| 281 | if((x&1)==0){ |
||
| 282 | ++r; |
||
| 283 | } |
||
| 284 | return r;
|
||
| 285 | }; |
||
| 286 | function _20(){ |
||
| 287 | for(var i=0;i<this.t;++i){ |
||
| 288 | if(this[i]!=0){ |
||
| 289 | return i*this._DB+_1f(this[i]); |
||
| 290 | } |
||
| 291 | } |
||
| 292 | if(this.s<0){ |
||
| 293 | return this.t*this._DB; |
||
| 294 | } |
||
| 295 | return -1; |
||
| 296 | }; |
||
| 297 | function _21(x){ |
||
| 298 | var r=0; |
||
| 299 | while(x!=0){ |
||
| 300 | x&=x-1;
|
||
| 301 | ++r; |
||
| 302 | } |
||
| 303 | return r;
|
||
| 304 | }; |
||
| 305 | function _22(){ |
||
| 306 | var r=0,x=this.s&this._DM; |
||
| 307 | for(var i=0;i<this.t;++i){ |
||
| 308 | r+=_21(this[i]^x);
|
||
| 309 | } |
||
| 310 | return r;
|
||
| 311 | }; |
||
| 312 | function _23(n){ |
||
| 313 | var j=Math.floor(n/this._DB); |
||
| 314 | if(j>=this.t){ |
||
| 315 | return (this.s!=0); |
||
| 316 | } |
||
| 317 | return ((this[j]&(1<<(n%this._DB)))!=0); |
||
| 318 | }; |
||
| 319 | function _24(n,op){ |
||
| 320 | var r=_1.ONE.shiftLeft(n);
|
||
| 321 | this._bitwiseTo(r,op,r);
|
||
| 322 | return r;
|
||
| 323 | }; |
||
| 324 | function _25(n){ |
||
| 325 | return this._changeBit(n,_f); |
||
| 326 | }; |
||
| 327 | function _26(n){ |
||
| 328 | return this._changeBit(n,_1a); |
||
| 329 | }; |
||
| 330 | function _27(n){ |
||
| 331 | return this._changeBit(n,_18); |
||
| 332 | }; |
||
| 333 | function _28(a,r){ |
||
| 334 | var i=0,c=0,m=Math.min(a.t,this.t); |
||
| 335 | while(i<m){
|
||
| 336 | c+=this[i]+a[i];
|
||
| 337 | r[i++]=c&this._DM;
|
||
| 338 | c>>=this._DB;
|
||
| 339 | } |
||
| 340 | if(a.t<this.t){ |
||
| 341 | c+=a.s; |
||
| 342 | while(i<this.t){ |
||
| 343 | c+=this[i];
|
||
| 344 | r[i++]=c&this._DM;
|
||
| 345 | c>>=this._DB;
|
||
| 346 | } |
||
| 347 | c+=this.s;
|
||
| 348 | }else{
|
||
| 349 | c+=this.s;
|
||
| 350 | while(i<a.t){
|
||
| 351 | c+=a[i]; |
||
| 352 | r[i++]=c&this._DM;
|
||
| 353 | c>>=this._DB;
|
||
| 354 | } |
||
| 355 | c+=a.s; |
||
| 356 | } |
||
| 357 | r.s=(c<0)?-1:0; |
||
| 358 | if(c>0){ |
||
| 359 | r[i++]=c; |
||
| 360 | }else{
|
||
| 361 | if(c<-1){ |
||
| 362 | r[i++]=this._DV+c;
|
||
| 363 | } |
||
| 364 | } |
||
| 365 | r.t=i; |
||
| 366 | r._clamp(); |
||
| 367 | }; |
||
| 368 | function _29(a){ |
||
| 369 | var r=_2();
|
||
| 370 | this._addTo(a,r);
|
||
| 371 | return r;
|
||
| 372 | }; |
||
| 373 | function _2a(a){ |
||
| 374 | var r=_2();
|
||
| 375 | this._subTo(a,r);
|
||
| 376 | return r;
|
||
| 377 | }; |
||
| 378 | function _2b(a){ |
||
| 379 | var r=_2();
|
||
| 380 | this._multiplyTo(a,r);
|
||
| 381 | return r;
|
||
| 382 | }; |
||
| 383 | function _2c(a){ |
||
| 384 | var r=_2();
|
||
| 385 | this._divRemTo(a,r,null); |
||
| 386 | return r;
|
||
| 387 | }; |
||
| 388 | function _2d(a){ |
||
| 389 | var r=_2();
|
||
| 390 | this._divRemTo(a,null,r); |
||
| 391 | return r;
|
||
| 392 | }; |
||
| 393 | function _2e(a){ |
||
| 394 | var q=_2(),r=_2();
|
||
| 395 | this._divRemTo(a,q,r);
|
||
| 396 | return [q,r];
|
||
| 397 | }; |
||
| 398 | function _2f(n){ |
||
| 399 | this[this.t]=this.am(0,n-1,this,0,0,this.t); |
||
| 400 | ++this.t;
|
||
| 401 | this._clamp();
|
||
| 402 | }; |
||
| 403 | function _30(n,w){ |
||
| 404 | while(this.t<=w){ |
||
| 405 | this[this.t++]=0; |
||
| 406 | } |
||
| 407 | this[w]+=n;
|
||
| 408 | while(this[w]>=this._DV){ |
||
| 409 | this[w]-=this._DV; |
||
| 410 | if(++w>=this.t){ |
||
| 411 | this[this.t++]=0; |
||
| 412 | } |
||
| 413 | ++this[w];
|
||
| 414 | } |
||
| 415 | }; |
||
| 416 | function _31(){ |
||
| 417 | }; |
||
| 418 | function _32(x){ |
||
| 419 | return x;
|
||
| 420 | }; |
||
| 421 | function _33(x,y,r){ |
||
| 422 | x._multiplyTo(y,r); |
||
| 423 | }; |
||
| 424 | function _34(x,r){ |
||
| 425 | x._squareTo(r); |
||
| 426 | }; |
||
| 427 | _31.prototype.convert=_32; |
||
| 428 | _31.prototype.revert=_32; |
||
| 429 | _31.prototype.mulTo=_33; |
||
| 430 | _31.prototype.sqrTo=_34; |
||
| 431 | function _35(e){ |
||
| 432 | return this._exp(e,new _31()); |
||
| 433 | }; |
||
| 434 | function _36(a,n,r){ |
||
| 435 | var i=Math.min(this.t+a.t,n); |
||
| 436 | r.s=0;
|
||
| 437 | r.t=i; |
||
| 438 | while(i>0){ |
||
| 439 | r[--i]=0;
|
||
| 440 | } |
||
| 441 | var j;
|
||
| 442 | for(j=r.t-this.t;i<j;++i){ |
||
| 443 | r[i+this.t]=this.am(0,a[i],r,i,0,this.t); |
||
| 444 | } |
||
| 445 | for(j=Math.min(a.t,n);i<j;++i){
|
||
| 446 | this.am(0,a[i],r,i,0,n-i); |
||
| 447 | } |
||
| 448 | r._clamp(); |
||
| 449 | }; |
||
| 450 | function _37(a,n,r){ |
||
| 451 | --n; |
||
| 452 | var i=r.t=this.t+a.t-n; |
||
| 453 | r.s=0;
|
||
| 454 | while(--i>=0){ |
||
| 455 | r[i]=0;
|
||
| 456 | } |
||
| 457 | for(i=Math.max(n-this.t,0);i<a.t;++i){ |
||
| 458 | r[this.t+i-n]=this.am(n-i,a[i],r,0,0,this.t+i-n); |
||
| 459 | } |
||
| 460 | r._clamp(); |
||
| 461 | r._drShiftTo(1,r);
|
||
| 462 | }; |
||
| 463 | function _38(m){ |
||
| 464 | this.r2=_2();
|
||
| 465 | this.q3=_2();
|
||
| 466 | _1.ONE._dlShiftTo(2*m.t,this.r2); |
||
| 467 | this.mu=this.r2.divide(m); |
||
| 468 | this.m=m;
|
||
| 469 | }; |
||
| 470 | function _39(x){ |
||
| 471 | if(x.s<0||x.t>2*this.m.t){ |
||
| 472 | return x.mod(this.m); |
||
| 473 | }else{
|
||
| 474 | if(x.compareTo(this.m)<0){ |
||
| 475 | return x;
|
||
| 476 | }else{
|
||
| 477 | var r=_2();
|
||
| 478 | x._copyTo(r); |
||
| 479 | this.reduce(r);
|
||
| 480 | return r;
|
||
| 481 | } |
||
| 482 | } |
||
| 483 | }; |
||
| 484 | function _3a(x){ |
||
| 485 | return x;
|
||
| 486 | }; |
||
| 487 | function _3b(x){ |
||
| 488 | x._drShiftTo(this.m.t-1,this.r2); |
||
| 489 | if(x.t>this.m.t+1){ |
||
| 490 | x.t=this.m.t+1; |
||
| 491 | x._clamp(); |
||
| 492 | } |
||
| 493 | this.mu._multiplyUpperTo(this.r2,this.m.t+1,this.q3); |
||
| 494 | this.m._multiplyLowerTo(this.q3,this.m.t+1,this.r2); |
||
| 495 | while(x.compareTo(this.r2)<0){ |
||
| 496 | x._dAddOffset(1,this.m.t+1); |
||
| 497 | } |
||
| 498 | x._subTo(this.r2,x);
|
||
| 499 | while(x.compareTo(this.m)>=0){ |
||
| 500 | x._subTo(this.m,x);
|
||
| 501 | } |
||
| 502 | }; |
||
| 503 | function _3c(x,r){ |
||
| 504 | x._squareTo(r); |
||
| 505 | this.reduce(r);
|
||
| 506 | }; |
||
| 507 | function _3d(x,y,r){ |
||
| 508 | x._multiplyTo(y,r); |
||
| 509 | this.reduce(r);
|
||
| 510 | }; |
||
| 511 | _38.prototype.convert=_39; |
||
| 512 | _38.prototype.revert=_3a; |
||
| 513 | _38.prototype.reduce=_3b; |
||
| 514 | _38.prototype.mulTo=_3d; |
||
| 515 | _38.prototype.sqrTo=_3c; |
||
| 516 | function _3e(e,m){ |
||
| 517 | var i=e.bitLength(),k,r=_3(1),z; |
||
| 518 | if(i<=0){ |
||
| 519 | return r;
|
||
| 520 | }else{
|
||
| 521 | if(i<18){ |
||
| 522 | k=1;
|
||
| 523 | }else{
|
||
| 524 | if(i<48){ |
||
| 525 | k=3;
|
||
| 526 | }else{
|
||
| 527 | if(i<144){ |
||
| 528 | k=4;
|
||
| 529 | }else{
|
||
| 530 | if(i<768){ |
||
| 531 | k=5;
|
||
| 532 | }else{
|
||
| 533 | k=6;
|
||
| 534 | } |
||
| 535 | } |
||
| 536 | } |
||
| 537 | } |
||
| 538 | } |
||
| 539 | if(i<8){ |
||
| 540 | z=new Classic(m);
|
||
| 541 | }else{
|
||
| 542 | if(m._isEven()){
|
||
| 543 | z=new _38(m);
|
||
| 544 | }else{
|
||
| 545 | z=new _5(m);
|
||
| 546 | } |
||
| 547 | } |
||
| 548 | var g=[],n=3,k1=k-1,km=(1<<k)-1; |
||
| 549 | g[1]=z.convert(this); |
||
| 550 | if(k>1){ |
||
| 551 | var g2=_2();
|
||
| 552 | z.sqrTo(g[1],g2);
|
||
| 553 | while(n<=km){
|
||
| 554 | g[n]=_2(); |
||
| 555 | z.mulTo(g2,g[n-2],g[n]);
|
||
| 556 | n+=2;
|
||
| 557 | } |
||
| 558 | } |
||
| 559 | var j=e.t-1,w,is1=true,r2=_2(),t; |
||
| 560 | i=_4(e[j])-1;
|
||
| 561 | while(j>=0){ |
||
| 562 | if(i>=k1){
|
||
| 563 | w=(e[j]>>(i-k1))&km; |
||
| 564 | }else{
|
||
| 565 | w=(e[j]&((1<<(i+1))-1))<<(k1-i); |
||
| 566 | if(j>0){ |
||
| 567 | w|=e[j-1]>>(this._DB+i-k1); |
||
| 568 | } |
||
| 569 | } |
||
| 570 | n=k; |
||
| 571 | while((w&1)==0){ |
||
| 572 | w>>=1;
|
||
| 573 | --n; |
||
| 574 | } |
||
| 575 | if((i-=n)<0){ |
||
| 576 | i+=this._DB;
|
||
| 577 | --j; |
||
| 578 | } |
||
| 579 | if(is1){
|
||
| 580 | g[w]._copyTo(r); |
||
| 581 | is1=false;
|
||
| 582 | }else{
|
||
| 583 | while(n>1){ |
||
| 584 | z.sqrTo(r,r2); |
||
| 585 | z.sqrTo(r2,r); |
||
| 586 | n-=2;
|
||
| 587 | } |
||
| 588 | if(n>0){ |
||
| 589 | z.sqrTo(r,r2); |
||
| 590 | }else{
|
||
| 591 | t=r; |
||
| 592 | r=r2; |
||
| 593 | r2=t; |
||
| 594 | } |
||
| 595 | z.mulTo(r2,g[w],r); |
||
| 596 | } |
||
| 597 | while(j>=0&&(e[j]&(1<<i))==0){ |
||
| 598 | z.sqrTo(r,r2); |
||
| 599 | t=r; |
||
| 600 | r=r2; |
||
| 601 | r2=t; |
||
| 602 | if(--i<0){ |
||
| 603 | i=this._DB-1; |
||
| 604 | --j; |
||
| 605 | } |
||
| 606 | } |
||
| 607 | } |
||
| 608 | return z.revert(r);
|
||
| 609 | }; |
||
| 610 | function _3f(a){ |
||
| 611 | var x=(this.s<0)?this.negate():this.clone(); |
||
| 612 | var y=(a.s<0)?a.negate():a.clone(); |
||
| 613 | if(x.compareTo(y)<0){ |
||
| 614 | var t=x;
|
||
| 615 | x=y; |
||
| 616 | y=t; |
||
| 617 | } |
||
| 618 | var i=x.getLowestSetBit(),g=y.getLowestSetBit();
|
||
| 619 | if(g<0){ |
||
| 620 | return x;
|
||
| 621 | } |
||
| 622 | if(i<g){
|
||
| 623 | g=i; |
||
| 624 | } |
||
| 625 | if(g>0){ |
||
| 626 | x._rShiftTo(g,x); |
||
| 627 | y._rShiftTo(g,y); |
||
| 628 | } |
||
| 629 | while(x.signum()>0){ |
||
| 630 | if((i=x.getLowestSetBit())>0){ |
||
| 631 | x._rShiftTo(i,x); |
||
| 632 | } |
||
| 633 | if((i=y.getLowestSetBit())>0){ |
||
| 634 | y._rShiftTo(i,y); |
||
| 635 | } |
||
| 636 | if(x.compareTo(y)>=0){ |
||
| 637 | x._subTo(y,x); |
||
| 638 | x._rShiftTo(1,x);
|
||
| 639 | }else{
|
||
| 640 | y._subTo(x,y); |
||
| 641 | y._rShiftTo(1,y);
|
||
| 642 | } |
||
| 643 | } |
||
| 644 | if(g>0){ |
||
| 645 | y._lShiftTo(g,y); |
||
| 646 | } |
||
| 647 | return y;
|
||
| 648 | }; |
||
| 649 | function _40(n){ |
||
| 650 | if(n<=0){ |
||
| 651 | return 0; |
||
| 652 | } |
||
| 653 | var d=this._DV%n,r=(this.s<0)?n-1:0; |
||
| 654 | if(this.t>0){ |
||
| 655 | if(d==0){ |
||
| 656 | r=this[0]%n; |
||
| 657 | }else{
|
||
| 658 | for(var i=this.t-1;i>=0;--i){ |
||
| 659 | r=(d*r+this[i])%n;
|
||
| 660 | } |
||
| 661 | } |
||
| 662 | } |
||
| 663 | return r;
|
||
| 664 | }; |
||
| 665 | function _41(m){ |
||
| 666 | var ac=m._isEven();
|
||
| 667 | if((this._isEven()&&ac)||m.signum()==0){ |
||
| 668 | return _1.ZERO;
|
||
| 669 | } |
||
| 670 | var u=m.clone(),v=this.clone(); |
||
| 671 | var a=_3(1),b=_3(0),c=_3(0),d=_3(1); |
||
| 672 | while(u.signum()!=0){ |
||
| 673 | while(u._isEven()){
|
||
| 674 | u._rShiftTo(1,u);
|
||
| 675 | if(ac){
|
||
| 676 | if(!a._isEven()||!b._isEven()){
|
||
| 677 | a._addTo(this,a);
|
||
| 678 | b._subTo(m,b); |
||
| 679 | } |
||
| 680 | a._rShiftTo(1,a);
|
||
| 681 | }else{
|
||
| 682 | if(!b._isEven()){
|
||
| 683 | b._subTo(m,b); |
||
| 684 | } |
||
| 685 | } |
||
| 686 | b._rShiftTo(1,b);
|
||
| 687 | } |
||
| 688 | while(v._isEven()){
|
||
| 689 | v._rShiftTo(1,v);
|
||
| 690 | if(ac){
|
||
| 691 | if(!c._isEven()||!d._isEven()){
|
||
| 692 | c._addTo(this,c);
|
||
| 693 | d._subTo(m,d); |
||
| 694 | } |
||
| 695 | c._rShiftTo(1,c);
|
||
| 696 | }else{
|
||
| 697 | if(!d._isEven()){
|
||
| 698 | d._subTo(m,d); |
||
| 699 | } |
||
| 700 | } |
||
| 701 | d._rShiftTo(1,d);
|
||
| 702 | } |
||
| 703 | if(u.compareTo(v)>=0){ |
||
| 704 | u._subTo(v,u); |
||
| 705 | if(ac){
|
||
| 706 | a._subTo(c,a); |
||
| 707 | } |
||
| 708 | b._subTo(d,b); |
||
| 709 | }else{
|
||
| 710 | v._subTo(u,v); |
||
| 711 | if(ac){
|
||
| 712 | c._subTo(a,c); |
||
| 713 | } |
||
| 714 | d._subTo(b,d); |
||
| 715 | } |
||
| 716 | } |
||
| 717 | if(v.compareTo(_1.ONE)!=0){ |
||
| 718 | return _1.ZERO;
|
||
| 719 | } |
||
| 720 | if(d.compareTo(m)>=0){ |
||
| 721 | return d.subtract(m);
|
||
| 722 | } |
||
| 723 | if(d.signum()<0){ |
||
| 724 | d._addTo(m,d); |
||
| 725 | }else{
|
||
| 726 | return d;
|
||
| 727 | } |
||
| 728 | if(d.signum()<0){ |
||
| 729 | return d.add(m);
|
||
| 730 | }else{
|
||
| 731 | return d;
|
||
| 732 | } |
||
| 733 | }; |
||
| 734 | 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]; |
||
| 735 | var _43=(1<<26)/_42[_42.length-1]; |
||
| 736 | function _44(t){ |
||
| 737 | var i,x=this.abs(); |
||
| 738 | if(x.t==1&&x[0]<=_42[_42.length-1]){ |
||
| 739 | for(i=0;i<_42.length;++i){ |
||
| 740 | if(x[0]==_42[i]){ |
||
| 741 | return true; |
||
| 742 | } |
||
| 743 | } |
||
| 744 | return false; |
||
| 745 | } |
||
| 746 | if(x._isEven()){
|
||
| 747 | return false; |
||
| 748 | } |
||
| 749 | i=1;
|
||
| 750 | while(i<_42.length){
|
||
| 751 | var m=_42[i],j=i+1; |
||
| 752 | while(j<_42.length&&m<_43){
|
||
| 753 | m*=_42[j++]; |
||
| 754 | } |
||
| 755 | m=x._modInt(m); |
||
| 756 | while(i<j){
|
||
| 757 | if(m%_42[i++]==0){ |
||
| 758 | return false; |
||
| 759 | } |
||
| 760 | } |
||
| 761 | } |
||
| 762 | return x._millerRabin(t);
|
||
| 763 | }; |
||
| 764 | function _45(t){ |
||
| 765 | var n1=this.subtract(_1.ONE); |
||
| 766 | var k=n1.getLowestSetBit();
|
||
| 767 | if(k<=0){ |
||
| 768 | return false; |
||
| 769 | } |
||
| 770 | var r=n1.shiftRight(k);
|
||
| 771 | t=(t+1)>>1; |
||
| 772 | if(t>_42.length){
|
||
| 773 | t=_42.length; |
||
| 774 | } |
||
| 775 | var a=_2();
|
||
| 776 | for(var i=0;i<t;++i){ |
||
| 777 | a._fromInt(_42[i]); |
||
| 778 | var y=a.modPow(r,this); |
||
| 779 | if(y.compareTo(_1.ONE)!=0&&y.compareTo(n1)!=0){ |
||
| 780 | var j=1; |
||
| 781 | while(j++<k&&y.compareTo(n1)!=0){ |
||
| 782 | y=y.modPowInt(2,this); |
||
| 783 | if(y.compareTo(_1.ONE)==0){ |
||
| 784 | return false; |
||
| 785 | } |
||
| 786 | } |
||
| 787 | if(y.compareTo(n1)!=0){ |
||
| 788 | return false; |
||
| 789 | } |
||
| 790 | } |
||
| 791 | } |
||
| 792 | return true; |
||
| 793 | }; |
||
| 794 | 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});
|
||
| 795 | })(); |
||
| 796 | } |