vnfmarket/src/main/webapp/vnfmarket/node_modules/socket.io-client/lib/vendor/web-socket-js/flash-src/com/hurlant/math/BigInteger.as

   1 /**\r
   2  * BigInteger\r
   3  * \r
   4  * An ActionScript 3 implementation of BigInteger (light version)\r
   5  * Copyright (c) 2007 Henri Torgemane\r
   6  * \r
   7  * Derived from:\r
   8  *              The jsbn library, Copyright (c) 2003-2005 Tom Wu\r
   9  * \r
  10  * See LICENSE.txt for full license information.\r
  11  */\r
  12 package com.hurlant.math\r
  13 {\r
  14 \r
  15         import com.hurlant.crypto.prng.Random;\r
  16         import com.hurlant.util.Hex;\r
  17         import com.hurlant.util.Memory;\r
  18         \r
  19         import flash.utils.ByteArray;\r
  20         use namespace bi_internal;\r
  21 \r
  22         public class BigInteger\r
  23         {\r
  24                 public static const DB:int = 30; // number of significant bits per chunk\r
  25                 public static const DV:int = (1<<DB);\r
  26                 public static const DM:int = (DV-1); // Max value in a chunk\r
  27                 \r
  28                 public static const BI_FP:int = 52;\r
  29                 public static const FV:Number = Math.pow(2, BI_FP);\r
  30                 public static const F1:int = BI_FP - DB;\r
  31                 public static const F2:int = 2*DB - BI_FP;\r
  32                 \r
  33                 public static const ZERO:BigInteger = nbv(0);\r
  34                 public static const ONE:BigInteger  = nbv(1);\r
  35                 \r
  36                 /*bi_internal */public var t:int; // number of chunks.\r
  37                 bi_internal var s:int; // sign\r
  38                 bi_internal var a:Array; // chunks\r
  39                 \r
  40                 /**\r
  41                  * \r
  42                  * @param value\r
  43                  * @param radix  WARNING: If value is ByteArray, this holds the number of bytes to use.\r
  44                  * @param unsigned\r
  45                  * \r
  46                  */\r
  47                 public function BigInteger(value:* = null, radix:int = 0, unsigned:Boolean = false) {\r
  48                         a = new Array;\r
  49                         if (value is String) {\r
  50                                 if (radix&&radix!=16) throw new Error("BigInteger construction with radix!=16 is not supported.");\r
  51                                 value = Hex.toArray(value);\r
  52                                 radix=0;\r
  53                         }\r
  54                         if (value is ByteArray) {\r
  55                                 var array:ByteArray = value as ByteArray;\r
  56                                 var length:int = radix || (array.length - array.position);\r
  57                                 fromArray(array, length, unsigned);\r
  58                         }\r
  59                 }\r
  60                 public function dispose():void {\r
  61                         var r:Random = new Random;\r
  62                         for (var i:uint=0;i<a.length;i++) {\r
  63                                 a[i] = r.nextByte();\r
  64                                 delete a[i];\r
  65                         }\r
  66                         a=null;\r
  67                         t=0;\r
  68                         s=0;\r
  69                         Memory.gc();\r
  70                 }\r
  71                 \r
  72                 public function toString(radix:Number=16):String {\r
  73                         if (s<0) return "-"+negate().toString(radix);\r
  74                         var k:int;\r
  75                         switch (radix) {\r
  76                                 case 2:   k=1; break;\r
  77                                 case 4:   k=2; break;\r
  78                                 case 8:   k=3; break;\r
  79                                 case 16:  k=4; break;\r
  80                                 case 32:  k=5; break;\r
  81                                 default:\r
  82 //                                      return toRadix(radix);\r
  83                         }\r
  84                         var km:int = (1<<k)-1;\r
  85                         var d:int = 0;\r
  86                         var m:Boolean = false;\r
  87                         var r:String = "";\r
  88                         var i:int = t;\r
  89                         var p:int = DB-(i*DB)%k;\r
  90                         if (i-->0) {\r
  91                                 if (p<DB && (d=a[i]>>p)>0) {\r
  92                                         m = true;\r
  93                                         r = d.toString(36);\r
  94                                 }\r
  95                                 while (i >= 0) {\r
  96                                         if (p<k) {\r
  97                                                 d = (a[i]&((1<<p)-1))<<(k-p);\r
  98                                                 d|= a[--i]>>(p+=DB-k);\r
  99                                         } else {\r
 100                                                 d = (a[i]>>(p-=k))&km;\r
 101                                                 if (p<=0) {\r
 102                                                         p += DB;\r
 103                                                         --i;\r
 104                                                 }\r
 105                                         }\r
 106                                         if (d>0) {\r
 107                                                 m = true;\r
 108                                         }\r
 109                                         if (m) {\r
 110                                                 r += d.toString(36);\r
 111                                         }\r
 112                                 }\r
 113                         }\r
 114                         return m?r:"0";\r
 115                 }\r
 116                 public function toArray(array:ByteArray):uint {\r
 117                         const k:int = 8;\r
 118                         const km:int = (1<<8)-1;\r
 119                         var d:int = 0;\r
 120                         var i:int = t;\r
 121                         var p:int = DB-(i*DB)%k;\r
 122                         var m:Boolean = false;\r
 123                         var c:int = 0;\r
 124                         if (i-->0) {\r
 125                                 if (p<DB && (d=a[i]>>p)>0) {\r
 126                                         m = true;\r
 127                                         array.writeByte(d);\r
 128                                         c++;\r
 129                                 }\r
 130                                 while (i >= 0) {\r
 131                                         if (p<k) {\r
 132                                                 d = (a[i]&((1<<p)-1))<<(k-p);\r
 133                                                 d|= a[--i]>>(p+=DB-k);\r
 134                                         } else {\r
 135                                                 d = (a[i]>>(p-=k))&km;\r
 136                                                 if (p<=0) {\r
 137                                                         p += DB;\r
 138                                                         --i;\r
 139                                                 }\r
 140                                         }\r
 141                                         if (d>0) {\r
 142                                                 m = true;\r
 143                                         }\r
 144                                         if (m) {\r
 145                                                 array.writeByte(d);\r
 146                                                 c++;\r
 147                                         }\r
 148                                 }\r
 149                         }\r
 150                         return c;\r
 151                 }\r
 152                 /**\r
 153                  * best-effort attempt to fit into a Number.\r
 154                  * precision can be lost if it just can't fit.\r
 155                  */\r
 156                 public function valueOf():Number {\r
 157                         if (s==-1) {\r
 158                                 return -negate().valueOf();\r
 159                         }\r
 160                         var coef:Number = 1;\r
 161                         var value:Number = 0;\r
 162                         for (var i:uint=0;i<t;i++) {\r
 163                                 value += a[i]*coef;\r
 164                                 coef *= DV;\r
 165                         }\r
 166                         return value;\r
 167                 }\r
 168                 /**\r
 169                  * -this\r
 170                  */\r
 171                 public function negate():BigInteger {\r
 172                         var r:BigInteger = nbi();\r
 173                         ZERO.subTo(this, r);\r
 174                         return r;\r
 175                 }\r
 176                 /**\r
 177                  * |this|\r
 178                  */\r
 179                 public function abs():BigInteger {\r
 180                         return (s<0)?negate():this;\r
 181                 }\r
 182                 /**\r
 183                  * return + if this > v, - if this < v, 0 if equal\r
 184                  */\r
 185                 public function compareTo(v:BigInteger):int {\r
 186                         var r:int = s - v.s;\r
 187                         if (r!=0) {\r
 188                                 return r;\r
 189                         }\r
 190                         var i:int = t;\r
 191                         r = i-v.t;\r
 192                         if (r!=0) {\r
 193                                 return r;\r
 194                         }\r
 195                         while (--i >=0) {\r
 196                                 r=a[i]-v.a[i];\r
 197                                 if (r != 0) return r;\r
 198                         }\r
 199                         return 0;\r
 200                 }\r
 201                 /**\r
 202                  * returns bit length of the integer x\r
 203                  */\r
 204                 bi_internal function nbits(x:int):int {\r
 205                         var r:int = 1;\r
 206                         var t:int;\r
 207                         if ((t=x>>>16) != 0) { x = t; r += 16; }\r
 208                         if ((t=x>>8) != 0) { x = t; r += 8; }\r
 209                         if ((t=x>>4) != 0) { x = t; r += 4; }\r
 210                         if ((t=x>>2) != 0) { x = t; r += 2; }\r
 211                         if ((t=x>>1) != 0) { x = t; r += 1; }\r
 212                         return r;\r
 213                 }\r
 214                 /**\r
 215                  * returns the number of bits in this\r
 216                  */\r
 217                 public function bitLength():int {\r
 218                         if (t<=0) return 0;\r
 219                         return DB*(t-1)+nbits(a[t-1]^(s&DM));\r
 220                 }\r
 221                 /**\r
 222                  * \r
 223                  * @param v\r
 224                  * @return this % v\r
 225                  * \r
 226                  */\r
 227                 public function mod(v:BigInteger):BigInteger {\r
 228                         var r:BigInteger = nbi();\r
 229                         abs().divRemTo(v,null,r);\r
 230                         if (s<0 && r.compareTo(ZERO)>0) {\r
 231                                 v.subTo(r,r);\r
 232                         }\r
 233                         return r;\r
 234                 }\r
 235                 /**\r
 236                  * this^e % m, 0 <= e < 2^32\r
 237                  */\r
 238                 public function modPowInt(e:int, m:BigInteger):BigInteger {\r
 239                         var z:IReduction;\r
 240                         if (e<256 || m.isEven()) {\r
 241                                 z = new ClassicReduction(m);\r
 242                         } else {\r
 243                                 z = new MontgomeryReduction(m);\r
 244                         }\r
 245                         return exp(e, z);\r
 246                 }\r
 247 \r
 248                 /**\r
 249                  * copy this to r\r
 250                  */\r
 251                 bi_internal function copyTo(r:BigInteger):void {\r
 252                         for (var i:int = t-1; i>=0; --i) {\r
 253                                 r.a[i] = a[i];\r
 254                         }\r
 255                         r.t = t;\r
 256                         r.s = s;\r
 257                 }\r
 258                 /**\r
 259                  * set from integer value "value", -DV <= value < DV\r
 260                  */\r
 261                 bi_internal function fromInt(value:int):void {\r
 262                         t = 1;\r
 263                         s = (value<0)?-1:0;\r
 264                         if (value>0) {\r
 265                                 a[0] = value;\r
 266                         } else if (value<-1) {\r
 267                                 a[0] = value+DV;\r
 268                         } else {\r
 269                                 t = 0;\r
 270                         }\r
 271                 }\r
 272                 /**\r
 273                  * set from ByteArray and length,\r
 274                  * starting a current position\r
 275                  * If length goes beyond the array, pad with zeroes.\r
 276                  */\r
 277                 bi_internal function fromArray(value:ByteArray, length:int, unsigned:Boolean = false):void {\r
 278                         var p:int = value.position;\r
 279                         var i:int = p+length;\r
 280                         var sh:int = 0;\r
 281                         const k:int = 8;\r
 282                         t = 0;\r
 283                         s = 0;\r
 284                         while (--i >= p) {\r
 285                                 var x:int = i<value.length?value[i]:0;\r
 286                                 if (sh == 0) {\r
 287                                         a[t++] = x;\r
 288                                 } else if (sh+k > DB) {\r
 289                                         a[t-1] |= (x&((1<<(DB-sh))-1))<<sh;\r
 290                                         a[t++] = x>>(DB-sh);\r
 291                                 } else {\r
 292                                         a[t-1] |= x<<sh;\r
 293                                 }\r
 294                                 sh += k;\r
 295                                 if (sh >= DB) sh -= DB;\r
 296                         }\r
 297                         if (!unsigned && (value[0]&0x80)==0x80) {\r
 298                                 s = -1;\r
 299                                 if (sh > 0) {\r
 300                                         a[t-1] |= ((1<<(DB-sh))-1)<<sh;\r
 301                                 }\r
 302                         }\r
 303                         clamp();\r
 304                         value.position = Math.min(p+length,value.length);\r
 305                 }\r
 306                 /**\r
 307                  * clamp off excess high words\r
 308                  */\r
 309                 bi_internal function clamp():void {\r
 310                         var c:int = s&DM;\r
 311                         while (t>0 && a[t-1]==c) {\r
 312                                 --t;\r
 313                         }\r
 314                 }\r
 315                 /**\r
 316                  * r = this << n*DB\r
 317                  */\r
 318                 bi_internal function dlShiftTo(n:int, r:BigInteger):void {\r
 319                         var i:int;\r
 320                         for (i=t-1; i>=0; --i) {\r
 321                                 r.a[i+n] = a[i];\r
 322                         }\r
 323                         for (i=n-1; i>=0; --i) {\r
 324                                 r.a[i] = 0;\r
 325                         }\r
 326                         r.t = t+n;\r
 327                         r.s = s;\r
 328                 }\r
 329                 /**\r
 330                  * r = this >> n*DB\r
 331                  */\r
 332                 bi_internal function drShiftTo(n:int, r:BigInteger):void {\r
 333                         var i:int;\r
 334                         for (i=n; i<t; ++i) {\r
 335                                 r.a[i-n] = a[i];\r
 336                         }\r
 337                         r.t = Math.max(t-n,0);\r
 338                         r.s = s;\r
 339                 }\r
 340                 /**\r
 341                  * r = this << n\r
 342                  */\r
 343                 bi_internal function lShiftTo(n:int, r:BigInteger):void {\r
 344                         var bs:int = n%DB;\r
 345                         var cbs:int = DB-bs;\r
 346                         var bm:int = (1<<cbs)-1;\r
 347                         var ds:int = n/DB;\r
 348                         var c:int = (s<<bs)&DM;\r
 349                         var i:int;\r
 350                         for (i=t-1; i>=0; --i) {\r
 351                                 r.a[i+ds+1] = (a[i]>>cbs)|c;\r
 352                                 c = (a[i]&bm)<<bs;\r
 353                         }\r
 354                         for (i=ds-1; i>=0; --i) {\r
 355                                 r.a[i] = 0;\r
 356                         }\r
 357                         r.a[ds] = c;\r
 358                         r.t = t+ds+1;\r
 359                         r.s = s;\r
 360                         r.clamp();\r
 361                 }\r
 362                 /**\r
 363                  * r = this >> n\r
 364                  */\r
 365                 bi_internal function rShiftTo(n:int, r:BigInteger):void {\r
 366                         r.s = s;\r
 367                         var ds:int = n/DB;\r
 368                         if (ds >= t) {\r
 369                                 r.t = 0;\r
 370                                 return;\r
 371                         }\r
 372                         var bs:int = n%DB;\r
 373                         var cbs:int = DB-bs;\r
 374                         var bm:int = (1<<bs)-1;\r
 375                         r.a[0] = a[ds]>>bs;\r
 376                         var i:int;\r
 377                         for (i=ds+1; i<t; ++i) {\r
 378                                 r.a[i-ds-1] |= (a[i]&bm)<<cbs;\r
 379                                 r.a[i-ds] = a[i]>>bs;\r
 380                         }\r
 381                         if (bs>0) {\r
 382                                 r.a[t-ds-1] |= (s&bm)<<cbs;\r
 383                         }\r
 384                         r.t = t-ds;\r
 385                         r.clamp();\r
 386                 }\r
 387                 /**\r
 388                  * r = this - v\r
 389                  */\r
 390                 bi_internal function subTo(v:BigInteger, r:BigInteger):void {\r
 391                         var i:int = 0;\r
 392                         var c:int = 0;\r
 393                         var m:int = Math.min(v.t, t);\r
 394                         while (i<m) {\r
 395                                 c += a[i] - v.a[i];\r
 396                                 r.a[i++] = c & DM;\r
 397                                 c >>= DB;\r
 398                         }\r
 399                         if (v.t < t) {\r
 400                                 c -= v.s;\r
 401                                 while (i< t) {\r
 402                                         c+= a[i];\r
 403                                         r.a[i++] = c&DM;\r
 404                                         c >>= DB;\r
 405                                 }\r
 406                                 c += s;\r
 407                         } else {\r
 408                                 c += s;\r
 409                                 while (i < v.t) {\r
 410                                         c -= v.a[i];\r
 411                                         r.a[i++] = c&DM;\r
 412                                         c >>= DB;\r
 413                                 }\r
 414                                 c -= v.s;\r
 415                         }\r
 416                         r.s = (c<0)?-1:0;\r
 417                         if (c<-1) {\r
 418                                 r.a[i++] = DV+c;\r
 419                         } else if (c>0) {\r
 420                                 r.a[i++] = c;\r
 421                         }\r
 422                         r.t = i;\r
 423                         r.clamp();\r
 424                 }\r
 425                 /**\r
 426                  * am: Compute w_j += (x*this_i), propagates carries,\r
 427                  * c is initial carry, returns final carry.\r
 428                  * c < 3*dvalue, x < 2*dvalue, this_i < dvalue\r
 429                  */\r
 430                 bi_internal function am(i:int,x:int,w:BigInteger,j:int,c:int,n:int):int {\r
 431                         var xl:int = x&0x7fff;\r
 432                         var xh:int = x>>15;\r
 433                         while(--n >= 0) {\r
 434                                 var l:int = a[i]&0x7fff;\r
 435                                 var h:int = a[i++]>>15;\r
 436                                 var m:int = xh*l + h*xl;\r
 437                                 l = xl*l + ((m&0x7fff)<<15)+w.a[j]+(c&0x3fffffff);\r
 438                                 c = (l>>>30)+(m>>>15)+xh*h+(c>>>30);\r
 439                                 w.a[j++] = l&0x3fffffff;\r
 440                         }\r
 441                         return c;\r
 442                 }\r
 443                 /**\r
 444                  * r = this * v, r != this,a (HAC 14.12)\r
 445                  * "this" should be the larger one if appropriate\r
 446                  */\r
 447                 bi_internal function multiplyTo(v:BigInteger, r:BigInteger):void {\r
 448                         var x:BigInteger = abs();\r
 449                         var y:BigInteger = v.abs();\r
 450                         var i:int = x.t;\r
 451                         r.t = i+y.t;\r
 452                         while (--i >= 0) {\r
 453                                 r.a[i] = 0;\r
 454                         }\r
 455                         for (i=0; i<y.t; ++i) {\r
 456                                 r.a[i+x.t] = x.am(0, y.a[i], r, i, 0, x.t);\r
 457                         }\r
 458                         r.s = 0;\r
 459                         r.clamp();\r
 460                         if (s!=v.s) {\r
 461                                 ZERO.subTo(r, r);\r
 462                         }\r
 463                 }\r
 464                 /**\r
 465                  * r = this^2, r != this (HAC 14.16)\r
 466                  */\r
 467                 bi_internal function squareTo(r:BigInteger):void {\r
 468                         var x:BigInteger = abs();\r
 469                         var i:int = r.t = 2*x.t;\r
 470                         while (--i>=0) r.a[i] = 0;\r
 471                         for (i=0; i<x.t-1; ++i) {\r
 472                                 var c:int = x.am(i, x.a[i], r, 2*i, 0, 1);\r
 473                                 if ((r.a[i+x.t] += x.am(i+1, 2*x.a[i], r, 2*i+1, c, x.t-i-1)) >= DV) {\r
 474                                         r.a[i+x.t] -= DV;\r
 475                                         r.a[i+x.t+1] = 1;\r
 476                                 }\r
 477                         }\r
 478                         if (r.t>0) {\r
 479                                 r.a[r.t-1] += x.am(i, x.a[i], r, 2*i, 0, 1);\r
 480                         }\r
 481                         r.s = 0;\r
 482                         r.clamp();\r
 483                 }\r
 484                 /**\r
 485                  * divide this by m, quotient and remainder to q, r (HAC 14.20)\r
 486                  * r != q, this != m. q or r may be null.\r
 487                  */\r
 488                 bi_internal function divRemTo(m:BigInteger, q:BigInteger = null, r:BigInteger = null):void {\r
 489                         var pm:BigInteger = m.abs();\r
 490                         if (pm.t <= 0) return;\r
 491                         var pt:BigInteger = abs();\r
 492                         if (pt.t < pm.t) {\r
 493                                 if (q!=null) q.fromInt(0);\r
 494                                 if (r!=null) copyTo(r);\r
 495                                 return;\r
 496                         }\r
 497                         if (r==null) r = nbi();\r
 498                         var y:BigInteger = nbi();\r
 499                         var ts:int = s;\r
 500                         var ms:int = m.s;\r
 501                         var nsh:int = DB-nbits(pm.a[pm.t-1]); // normalize modulus\r
 502                         if (nsh>0) {\r
 503                                 pm.lShiftTo(nsh, y);\r
 504                                 pt.lShiftTo(nsh, r);\r
 505                         } else {\r
 506                                 pm.copyTo(y);\r
 507                                 pt.copyTo(r);\r
 508                         }\r
 509                         var ys:int = y.t;\r
 510                         var y0:int = y.a[ys-1];\r
 511                         if (y0==0) return;\r
 512                         var yt:Number = y0*(1<<F1)+((ys>1)?y.a[ys-2]>>F2:0);\r
 513                         var d1:Number = FV/yt;\r
 514                         var d2:Number = (1<<F1)/yt;\r
 515                         var e:Number = 1<<F2;\r
 516                         var i:int = r.t;\r
 517                         var j:int = i-ys;\r
 518                         var t:BigInteger = (q==null)?nbi():q;\r
 519                         y.dlShiftTo(j,t);\r
 520                         if (r.compareTo(t)>=0) {\r
 521                                 r.a[r.t++] = 1;\r
 522                                 r.subTo(t,r);\r
 523                         }\r
 524                         ONE.dlShiftTo(ys,t);\r
 525                         t.subTo(y,y); // "negative" y so we can replace sub with am later.\r
 526                         while(y.t<ys) y.(y.t++, 0);\r
 527                         while(--j >= 0) {\r
 528                                 // Estimate quotient digit\r
 529                                 var qd:int = (r.a[--i]==y0)?DM:Number(r.a[i])*d1+(Number(r.a[i-1])+e)*d2;\r
 530                                 if ((r.a[i]+= y.am(0, qd, r, j, 0, ys))<qd) { // Try it out\r
 531                                         y.dlShiftTo(j, t);\r
 532                                         r.subTo(t,r);\r
 533                                         while (r.a[i]<--qd) {\r
 534                                                 r.subTo(t,r);\r
 535                                         }\r
 536                                 }\r
 537                         }\r
 538                         if (q!=null) {\r
 539                                 r.drShiftTo(ys,q);\r
 540                                 if (ts!=ms) {\r
 541                                         ZERO.subTo(q,q);\r
 542                                 }\r
 543                         }\r
 544                         r.t = ys;\r
 545                         r.clamp();\r
 546                         if (nsh>0) {\r
 547                                 r.rShiftTo(nsh, r); // Denormalize remainder\r
 548                         }\r
 549                         if (ts<0) {\r
 550                                 ZERO.subTo(r,r);\r
 551                         }\r
 552                 }\r
 553                 /**\r
 554                  * return "-1/this % 2^DB"; useful for Mont. reduction\r
 555                  * justification:\r
 556                  *         xy == 1 (mod n)\r
 557                  *         xy =  1+km\r
 558                  *       xy(2-xy) = (1+km)(1-km)\r
 559                  * x[y(2-xy)] =  1-k^2.m^2\r
 560                  * x[y(2-xy)] == 1 (mod m^2)\r
 561                  * if y is 1/x mod m, then y(2-xy) is 1/x mod m^2\r
 562                  * should reduce x and y(2-xy) by m^2 at each step to keep size bounded\r
 563                  * [XXX unit test the living shit out of this.]\r
 564                  */\r
 565                 bi_internal function invDigit():int {\r
 566                         if (t<1) return 0;\r
 567                         var x:int = a[0];\r
 568                         if ((x&1)==0) return 0;\r
 569                         var y:int = x&3;                                                        // y == 1/x mod 2^2\r
 570                         y = (y*(2-(x&0xf )*y))             &0xf;        // y == 1/x mod 2^4\r
 571                         y = (y*(2-(x&0xff)*y))             &0xff;       // y == 1/x mod 2^8\r
 572                         y = (y*(2-(((x&0xffff)*y)&0xffff)))&0xffff;     // y == 1/x mod 2^16\r
 573                         // last step - calculate inverse mod DV directly;\r
 574                         // assumes 16 < DB <= 32 and assumes ability to handle 48-bit ints\r
 575                         // XXX 48 bit ints? Whaaaa? is there an implicit float conversion in here?\r
 576                         y = (y*(2-x*y%DV))%DV;  // y == 1/x mod 2^dbits\r
 577                         // we really want the negative inverse, and -DV < y < DV\r
 578                         return (y>0)?DV-y:-y;\r
 579                 }\r
 580                 /**\r
 581                  * true iff this is even\r
 582                  */\r
 583                 bi_internal function isEven():Boolean {\r
 584                         return ((t>0)?(a[0]&1):s) == 0;\r
 585                 }\r
 586                 /**\r
 587                  * this^e, e < 2^32, doing sqr and mul with "r" (HAC 14.79)\r
 588                  */\r
 589                 bi_internal function exp(e:int, z:IReduction):BigInteger {\r
 590                         if (e > 0xffffffff || e < 1) return ONE;\r
 591                         var r:BigInteger = nbi();\r
 592                         var r2:BigInteger = nbi();\r
 593                         var g:BigInteger = z.convert(this);\r
 594                         var i:int = nbits(e)-1;\r
 595                         g.copyTo(r);\r
 596                         while(--i>=0) {\r
 597                                 z.sqrTo(r, r2);\r
 598                                 if ((e&(1<<i))>0) {\r
 599                                         z.mulTo(r2,g,r);\r
 600                                 } else {\r
 601                                         var t:BigInteger = r;\r
 602                                         r = r2;\r
 603                                         r2 = t;\r
 604                                 }\r
 605                                 \r
 606                         }\r
 607                         return z.revert(r);\r
 608                 }\r
 609                 bi_internal function intAt(str:String, index:int):int {\r
 610                         return parseInt(str.charAt(index), 36);\r
 611                 }\r
 612 \r
 613 \r
 614                 protected function nbi():* {\r
 615                         return new BigInteger;\r
 616                 }\r
 617                 /**\r
 618                  * return bigint initialized to value\r
 619                  */\r
 620                 public static function nbv(value:int):BigInteger {\r
 621                         var bn:BigInteger = new BigInteger;\r
 622                         bn.fromInt(value);\r
 623                         return bn;\r
 624                 }\r
 625 \r
 626 \r
 627                 // Functions above are sufficient for RSA encryption.\r
 628                 // The stuff below is useful for decryption and key generation\r
 629 \r
 630                 public static const lowprimes:Array = [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];\r
 631                 public static const lplim:int = (1<<26)/lowprimes[lowprimes.length-1];\r
 632 \r
 633 \r
 634                 public function clone():BigInteger {\r
 635                         var r:BigInteger = new BigInteger;\r
 636                         this.copyTo(r);\r
 637                         return r;\r
 638                 }\r
 639                 \r
 640                 /**\r
 641                  * \r
 642                  * @return value as integer\r
 643                  * \r
 644                  */\r
 645                 public function intValue():int {\r
 646                         if (s<0) {\r
 647                                 if (t==1) {\r
 648                                         return a[0]-DV;\r
 649                                 } else if (t==0) {\r
 650                                         return -1;\r
 651                                 }\r
 652                         } else if (t==1) {\r
 653                                 return a[0];\r
 654                         } else if (t==0) {\r
 655                                 return 0;\r
 656                         }\r
 657                         // assumes 16 < DB < 32\r
 658                         return  ((a[1]&((1<<(32-DB))-1))<<DB)|a[0];\r
 659                 }\r
 660                 \r
 661                 /**\r
 662                  * \r
 663                  * @return value as byte\r
 664                  * \r
 665                  */\r
 666                 public function byteValue():int {\r
 667                         return (t==0)?s:(a[0]<<24)>>24;\r
 668                 }\r
 669                 \r
 670                 /**\r
 671                  * \r
 672                  * @return value as short (assumes DB>=16)\r
 673                  * \r
 674                  */\r
 675                 public function shortValue():int {\r
 676                         return (t==0)?s:(a[0]<<16)>>16;\r
 677                 }\r
 678                 \r
 679                 /**\r
 680                  * \r
 681                  * @param r\r
 682                  * @return x s.t. r^x < DV\r
 683                  * \r
 684                  */\r
 685                 protected function chunkSize(r:Number):int {\r
 686                         return Math.floor(Math.LN2*DB/Math.log(r));\r
 687                 }\r
 688                 \r
 689                 /**\r
 690                  * \r
 691                  * @return 0 if this ==0, 1 if this >0\r
 692                  * \r
 693                  */\r
 694                 public function sigNum():int {\r
 695                         if (s<0) {\r
 696                                 return -1;\r
 697                         } else if (t<=0 || (t==1 && a[0]<=0)) {\r
 698                                 return 0;\r
 699                         } else{\r
 700                                 return 1;\r
 701                         }\r
 702                 }\r
 703                 \r
 704                 /**\r
 705                  * \r
 706                  * @param b: radix to use\r
 707                  * @return a string representing the integer converted to the radix.\r
 708                  * \r
 709                  */\r
 710                 protected function toRadix(b:uint=10):String {\r
 711                         if (sigNum()==0 || b<2 || b>32) return "0";\r
 712                         var cs:int = chunkSize(b);\r
 713                         var a:Number = Math.pow(b, cs);\r
 714                         var d:BigInteger = nbv(a);\r
 715                         var y:BigInteger = nbi();\r
 716                         var z:BigInteger = nbi();\r
 717                         var r:String = "";\r
 718                         divRemTo(d, y, z);\r
 719                         while (y.sigNum()>0) {\r
 720                                 r = (a+z.intValue()).toString(b).substr(1) + r;\r
 721                                 y.divRemTo(d,y,z);\r
 722                         }\r
 723                         return z.intValue().toString(b) + r;\r
 724                 }\r
 725                 \r
 726                 /**\r
 727                  * \r
 728                  * @param s a string to convert from using radix.\r
 729                  * @param b a radix\r
 730                  * \r
 731                  */\r
 732                 protected function fromRadix(s:String, b:int = 10):void {\r
 733                         fromInt(0);\r
 734                         var cs:int = chunkSize(b);\r
 735                         var d:Number = Math.pow(b, cs);\r
 736                         var mi:Boolean = false;\r
 737                         var j:int = 0;\r
 738                         var w:int = 0;\r
 739                         for (var i:int=0;i<s.length;++i) {\r
 740                                 var x:int = intAt(s, i);\r
 741                                 if (x<0) {\r
 742                                         if (s.charAt(i) == "-" && sigNum() == 0) {\r
 743                                                 mi = true;\r
 744                                         }\r
 745                                         continue;\r
 746                                 }\r
 747                                 w = b*w+x;\r
 748                                 if (++j >= cs) {\r
 749                                         dMultiply(d);\r
 750                                         dAddOffset(w,0);\r
 751                                         j=0;\r
 752                                         w=0;\r
 753                                 }\r
 754                         }\r
 755                         if (j>0) {\r
 756                                 dMultiply(Math.pow(b,j));\r
 757                                 dAddOffset(w,0);\r
 758                         }\r
 759                         if (mi) {\r
 760                                 BigInteger.ZERO.subTo(this, this);\r
 761                         }\r
 762                 }\r
 763                 \r
 764                 // XXX function fromNumber not written yet.\r
 765                 \r
 766                 /**\r
 767                  * \r
 768                  * @return a byte array.\r
 769                  * \r
 770                  */\r
 771                 public function toByteArray():ByteArray {\r
 772                         var i:int = t;\r
 773                         var r:ByteArray = new ByteArray;\r
 774                         r[0] = s;\r
 775                         var p:int = DB-(i*DB)%8;\r
 776                         var d:int;\r
 777                         var k:int=0;\r
 778                         if (i-->0) {\r
 779                                 if (p<DB && (d=a[i]>>p)!=(s&DM)>>p) {\r
 780                                         r[k++] = d|(s<<(DB-p));\r
 781                                 }\r
 782                                 while (i>=0) {\r
 783                                         if(p<8) {\r
 784                                                 d = (a[i]&((1<<p)-1))<<(8-p);\r
 785                                                 d|= a[--i]>>(p+=DB-8);\r
 786                                         } else {\r
 787                                                 d = (a[i]>>(p-=8))&0xff;\r
 788                                                 if (p<=0) {\r
 789                                                         p += DB;\r
 790                                                         --i;\r
 791                                                 }\r
 792                                         }\r
 793                                         if ((d&0x80)!=0) d|=-256;\r
 794                                         if (k==0 && (s&0x80)!=(d&0x80)) ++k;\r
 795                                         if (k>0 || d!=s) r[k++] = d;\r
 796                                 } \r
 797                         }\r
 798                         return r;\r
 799                 }\r
 800 \r
 801                 public function equals(a:BigInteger):Boolean {\r
 802                         return compareTo(a)==0;\r
 803                 }\r
 804                 public function min(a:BigInteger):BigInteger {\r
 805                         return (compareTo(a)<0)?this:a;\r
 806                 }\r
 807                 public function max(a:BigInteger):BigInteger {\r
 808                         return (compareTo(a)>0)?this:a;\r
 809                 }\r
 810                 \r
 811                 /**\r
 812                  * \r
 813                  * @param a     a BigInteger to perform the operation with\r
 814                  * @param op a Function implementing the operation\r
 815                  * @param r a BigInteger to store the result of the operation\r
 816                  * \r
 817                  */\r
 818                 protected function bitwiseTo(a:BigInteger, op:Function, r:BigInteger):void {\r
 819                         var i:int;\r
 820                         var f:int;\r
 821                         var m:int = Math.min(a.t, t);\r
 822                         for (i=0; i<m; ++i) {\r
 823                                 r.a[i] = op(this.a[i],a.a[i]);\r
 824                         }\r
 825                         if (a.t<t) {\r
 826                                 f = a.s&DM;\r
 827                                 for (i=m;i<t;++i) {\r
 828                                         r.a[i] = op(this.a[i],f);\r
 829                                 }\r
 830                                 r.t = t;\r
 831                         } else {\r
 832                                 f = s&DM;\r
 833                                 for (i=m;i<a.t;++i) {\r
 834                                         r.a[i] = op(f,a.a[i]);\r
 835                                 }\r
 836                                 r.t = a.t;\r
 837                         }\r
 838                         r.s = op(s, a.s);\r
 839                         r.clamp();\r
 840                 }\r
 841                 \r
 842                 private function op_and(x:int, y:int):int {return x&y;}\r
 843                 public function and(a:BigInteger):BigInteger {\r
 844                         var r:BigInteger = new BigInteger;\r
 845                         bitwiseTo(a, op_and, r);\r
 846                         return r;\r
 847                 }\r
 848                 \r
 849                 private function op_or(x:int, y:int):int {return x|y;}\r
 850                 public function or(a:BigInteger):BigInteger {\r
 851                         var r:BigInteger = new BigInteger;\r
 852                         bitwiseTo(a, op_or, r);\r
 853                         return r;\r
 854                 }\r
 855                 \r
 856                 private function op_xor(x:int, y:int):int {return x^y;}\r
 857                 public function xor(a:BigInteger):BigInteger {\r
 858                         var r:BigInteger = new BigInteger;\r
 859                         bitwiseTo(a, op_xor, r);\r
 860                         return r;\r
 861                 }\r
 862                 \r
 863                 private function op_andnot(x:int, y:int):int { return x&~y;}\r
 864                 public function andNot(a:BigInteger):BigInteger {\r
 865                         var r:BigInteger = new BigInteger;\r
 866                         bitwiseTo(a, op_andnot, r);\r
 867                         return r;\r
 868                 }\r
 869                 \r
 870                 public function not():BigInteger {\r
 871                         var r:BigInteger = new BigInteger;\r
 872                         for (var i:int=0;i<t;++i) {\r
 873                                 r[i] = DM&~a[i];\r
 874                         }\r
 875                         r.t = t;\r
 876                         r.s = ~s;\r
 877                         return r;\r
 878                 }\r
 879                 \r
 880                 public function shiftLeft(n:int):BigInteger {\r
 881                         var r:BigInteger = new BigInteger;\r
 882                         if (n<0) {\r
 883                                 rShiftTo(-n, r);\r
 884                         } else {\r
 885                                 lShiftTo(n, r);\r
 886                         }\r
 887                         return r;\r
 888                 }\r
 889                 public function shiftRight(n:int):BigInteger {\r
 890                         var r:BigInteger = new BigInteger;\r
 891                         if (n<0) {\r
 892                                 lShiftTo(-n, r);\r
 893                         } else {\r
 894                                 rShiftTo(n, r);\r
 895                         }\r
 896                         return r;\r
 897                 }\r
 898                 \r
 899                 /**\r
 900                  * \r
 901                  * @param x\r
 902                  * @return index of lowet 1-bit in x, x < 2^31\r
 903                  * \r
 904                  */\r
 905                 private function lbit(x:int):int {\r
 906                         if (x==0) return -1;\r
 907                         var r:int = 0;\r
 908                         if ((x&0xffff)==0) { x>>= 16; r += 16; }\r
 909                         if ((x&0xff) == 0) { x>>=  8; r +=  8; }\r
 910                         if ((x&0xf)  == 0) { x>>=  4; r +=  4; }\r
 911                         if ((x&0x3)  == 0) { x>>=  2; r +=  2; }\r
 912                         if ((x&0x1)  == 0) ++r;\r
 913                         return r;\r
 914                 }\r
 915                 \r
 916                 /**\r
 917                  * \r
 918                  * @return index of lowest 1-bit (or -1 if none)\r
 919                  * \r
 920                  */\r
 921                 public function getLowestSetBit():int {\r
 922                         for (var i:int=0;i<t;++i) {\r
 923                                 if (a[i]!=0) return i*DB+lbit(a[i]);\r
 924                         }\r
 925                         if (s<0) return t*DB;\r
 926                         return -1;\r
 927                 }\r
 928                 \r
 929                 /**\r
 930                  * \r
 931                  * @param x\r
 932                  * @return number of 1 bits in x\r
 933                  * \r
 934                  */\r
 935                 private function cbit(x:int):int {\r
 936                         var r:uint =0;\r
 937                         while (x!=0) { x &= x-1; ++r }\r
 938                         return r;\r
 939                 }\r
 940                 \r
 941                 /**\r
 942                  * \r
 943                  * @return number of set bits\r
 944                  * \r
 945                  */\r
 946                 public function bitCount():int {\r
 947                         var r:int=0;\r
 948                         var x:int = s&DM;\r
 949                         for (var i:int=0;i<t;++i) {\r
 950                                 r += cbit(a[i]^x);\r
 951                         }\r
 952                         return r;\r
 953                 }\r
 954                 \r
 955                 /**\r
 956                  * \r
 957                  * @param n\r
 958                  * @return true iff nth bit is set\r
 959                  * \r
 960                  */\r
 961                 public function testBit(n:int):Boolean {\r
 962                         var j:int = Math.floor(n/DB);\r
 963                         if (j>=t) {\r
 964                                 return s!=0;\r
 965                         }\r
 966                         return ((a[j]&(1<<(n%DB)))!=0);\r
 967                 }\r
 968                 \r
 969                 /**\r
 970                  * \r
 971                  * @param n\r
 972                  * @param op\r
 973                  * @return this op (1<<n)\r
 974                  * \r
 975                  */\r
 976                 protected function changeBit(n:int,op:Function):BigInteger {\r
 977                         var r:BigInteger = BigInteger.ONE.shiftLeft(n);\r
 978                         bitwiseTo(r, op, r);\r
 979                         return r;\r
 980                 }\r
 981                 \r
 982                 /**\r
 983                  * \r
 984                  * @param n\r
 985                  * @return this | (1<<n)\r
 986                  * \r
 987                  */\r
 988                 public function setBit(n:int):BigInteger { return changeBit(n, op_or); }\r
 989 \r
 990                 /**\r
 991                  * \r
 992                  * @param n\r
 993                  * @return this & ~(1<<n)\r
 994                  * \r
 995                  */\r
 996                 public function clearBit(n:int):BigInteger { return changeBit(n, op_andnot); }\r
 997 \r
 998                 /**\r
 999                  * \r
1000                  * @param n\r
1001                  * @return this ^ (1<<n)\r
1002                  * \r
1003                  */\r
1004                 public function flipBit(n:int):BigInteger { return changeBit(n, op_xor); }\r
1005 \r
1006                 /**\r
1007                  * \r
1008                  * @param a\r
1009                  * @param r = this + a\r
1010                  * \r
1011                  */\r
1012                 protected function addTo(a:BigInteger, r:BigInteger):void {\r
1013                         var i:int = 0;\r
1014                         var c:int = 0;\r
1015                         var m:int = Math.min(a.t, t);\r
1016                         while (i<m) {\r
1017                                 c += this.a[i] + a.a[i];\r
1018                                 r.a[i++] = c&DM;\r
1019                                 c>>=DB;\r
1020                         }\r
1021                         if (a.t < t) {\r
1022                                 c += a.s;\r
1023                                 while (i<t) {\r
1024                                         c += this.a[i];\r
1025                                         r.a[i++] = c&DM;\r
1026                                         c >>= DB;\r
1027                                 }\r
1028                                 c += s;\r
1029                         } else {\r
1030                                 c += s;\r
1031                                 while (i<a.t) {\r
1032                                         c += a.a[i];\r
1033                                         r.a[i++] = c&DM;\r
1034                                         c >>= DB;\r
1035                                 }\r
1036                                 c += a.s;\r
1037                         }\r
1038                         r.s = (c<0)?-1:0;\r
1039                         if (c>0) {\r
1040                                 r.a[i++] = c;\r
1041                         } else if (c<-1) {\r
1042                                 r.a[i++] = DV+c;\r
1043                         }\r
1044                         r.t = i;\r
1045                         r.clamp();\r
1046                 }\r
1047                 \r
1048                 /**\r
1049                  * \r
1050                  * @param a\r
1051                  * @return this + a\r
1052                  * \r
1053                  */\r
1054                 public function add(a:BigInteger):BigInteger {\r
1055                         var r:BigInteger = new BigInteger;\r
1056                         addTo(a,r);\r
1057                         return r;\r
1058                 }\r
1059 \r
1060                 /**\r
1061                  * \r
1062                  * @param a\r
1063                  * @return this - a\r
1064                  * \r
1065                  */\r
1066                 public function subtract(a:BigInteger):BigInteger {\r
1067                         var r:BigInteger = new BigInteger;\r
1068                         subTo(a,r);\r
1069                         return r;\r
1070                 }\r
1071                 \r
1072                 /**\r
1073                  * \r
1074                  * @param a\r
1075                  * @return this * a\r
1076                  * \r
1077                  */\r
1078                 public function multiply(a:BigInteger):BigInteger {\r
1079                         var r:BigInteger = new BigInteger;\r
1080                         multiplyTo(a,r);\r
1081                         return r;\r
1082                 }\r
1083                 \r
1084                 /**\r
1085                  * \r
1086                  * @param a\r
1087                  * @return this / a\r
1088                  * \r
1089                  */\r
1090                 public function divide(a:BigInteger):BigInteger {\r
1091                         var r:BigInteger = new BigInteger;\r
1092                         divRemTo(a, r, null);\r
1093                         return r;\r
1094                 }\r
1095                 \r
1096                 public function remainder(a:BigInteger):BigInteger {\r
1097                         var r:BigInteger = new BigInteger;\r
1098                         divRemTo(a, null, r);\r
1099                         return r;\r
1100                 }\r
1101                 \r
1102                 /**\r
1103                  * \r
1104                  * @param a\r
1105                  * @return [this/a, this%a]\r
1106                  * \r
1107                  */\r
1108                 public function divideAndRemainder(a:BigInteger):Array {\r
1109                         var q:BigInteger = new BigInteger;\r
1110                         var r:BigInteger = new BigInteger;\r
1111                         divRemTo(a, q, r);\r
1112                         return [q,r];\r
1113                 }\r
1114                 \r
1115                 /**\r
1116                  * \r
1117                  * this *= n, this >=0, 1 < n < DV\r
1118                  * \r
1119                  * @param n\r
1120                  * \r
1121                  */\r
1122                 bi_internal function dMultiply(n:int):void {\r
1123                         a[t] = am(0, n-1, this, 0, 0, t);\r
1124                         ++t;\r
1125                         clamp();\r
1126                 }\r
1127                 \r
1128                 /**\r
1129                  * \r
1130                  * this += n << w words, this >= 0\r
1131                  * \r
1132                  * @param n\r
1133                  * @param w\r
1134                  * \r
1135                  */\r
1136                 bi_internal function dAddOffset(n:int, w:int):void {\r
1137                         while (t<=w) {\r
1138                                 a[t++] = 0;\r
1139                         }\r
1140                         a[w] += n;\r
1141                         while (a[w] >= DV) {\r
1142                                 a[w] -= DV;\r
1143                                 if (++w >= t) {\r
1144                                         a[t++] = 0;\r
1145                                 }\r
1146                                 ++a[w];\r
1147                         }\r
1148                 }\r
1149 \r
1150                 /**\r
1151                  * \r
1152                  * @param e\r
1153                  * @return this^e\r
1154                  * \r
1155                  */\r
1156                 public function pow(e:int):BigInteger {\r
1157                         return exp(e, new NullReduction);\r
1158                 }\r
1159                 \r
1160                 /**\r
1161                  * \r
1162                  * @param a\r
1163                  * @param n\r
1164                  * @param r = lower n words of "this * a", a.t <= n\r
1165                  * \r
1166                  */\r
1167                 bi_internal function multiplyLowerTo(a:BigInteger, n:int, r:BigInteger):void {\r
1168                         var i:int = Math.min(t+a.t, n);\r
1169                         r.s = 0; // assumes a, this >= 0\r
1170                         r.t = i;\r
1171                         while (i>0) {\r
1172                                 r.a[--i]=0;\r
1173                         }\r
1174                         var j:int;\r
1175                         for (j=r.t-t;i<j;++i) {\r
1176                                 r.a[i+t] = am(0, a.a[i], r, i, 0, t);\r
1177                         }\r
1178                         for (j=Math.min(a.t,n);i<j;++i) {\r
1179                                 am(0, a.a[i], r, i, 0, n-i);\r
1180                         }\r
1181                         r.clamp();\r
1182                 }\r
1183                 \r
1184                 /**\r
1185                  * \r
1186                  * @param a\r
1187                  * @param n\r
1188                  * @param r = "this * a" without lower n words, n > 0\r
1189                  * \r
1190                  */\r
1191                 bi_internal function multiplyUpperTo(a:BigInteger, n:int, r:BigInteger):void {\r
1192                         --n;\r
1193                         var i:int = r.t = t+a.t-n;\r
1194                         r.s = 0; // assumes a,this >= 0\r
1195                         while (--i>=0) {\r
1196                                 r.a[i] = 0;\r
1197                         }\r
1198                         for (i=Math.max(n-t,0);i<a.t;++i) {\r
1199                                 r.a[t+i-n] = am(n-i, a.a[i], r, 0, 0, t+i-n);\r
1200                         }\r
1201                         r.clamp();\r
1202                         r.drShiftTo(1,r);\r
1203                 }\r
1204                 \r
1205                 /**\r
1206                  * \r
1207                  * @param e\r
1208                  * @param m\r
1209                  * @return this^e % m (HAC 14.85)\r
1210                  * \r
1211                  */\r
1212                 public function modPow(e:BigInteger, m:BigInteger):BigInteger {\r
1213                         var i:int = e.bitLength();\r
1214                         var k:int;\r
1215                         var r:BigInteger = nbv(1);\r
1216                         var z:IReduction;\r
1217                         \r
1218                         if (i<=0) {\r
1219                                 return r;\r
1220                         } else if (i<18) {\r
1221                                 k=1;\r
1222                         } else if (i<48) {\r
1223                                 k=3;\r
1224                         } else if (i<144) {\r
1225                                 k=4;\r
1226                         } else if (i<768) {\r
1227                                 k=5;\r
1228                         } else {\r
1229                                 k=6;\r
1230                         }\r
1231                         if (i<8) {\r
1232                                 z = new ClassicReduction(m);\r
1233                         } else if (m.isEven()) {\r
1234                                 z = new BarrettReduction(m);\r
1235                         } else {\r
1236                                 z = new MontgomeryReduction(m);\r
1237                         }\r
1238                         // precomputation\r
1239                         var g:Array = [];\r
1240                         var n:int = 3;\r
1241                         var k1:int = k-1;\r
1242                         var km:int = (1<<k)-1;\r
1243                         g[1] = z.convert(this);\r
1244                         if (k > 1) {\r
1245                                 var g2:BigInteger = new BigInteger;\r
1246                                 z.sqrTo(g[1], g2);\r
1247                                 while (n<=km) {\r
1248                                         g[n] = new BigInteger;\r
1249                                         z.mulTo(g2, g[n-2], g[n]);\r
1250                                         n += 2;\r
1251                                 }\r
1252                         }\r
1253                         \r
1254                         var j:int = e.t-1;\r
1255                         var w:int;\r
1256                         var is1:Boolean = true;\r
1257                         var r2:BigInteger = new BigInteger;\r
1258                         var t:BigInteger;\r
1259                         i = nbits(e.a[j])-1;\r
1260                         while (j>=0) {\r
1261                                 if (i>=k1) {\r
1262                                         w = (e.a[j]>>(i-k1))&km;\r
1263                                 } else {\r
1264                                         w = (e.a[j]&((1<<(i+1))-1))<<(k1-i);\r
1265                                         if (j>0) {\r
1266                                                 w |= e.a[j-1]>>(DB+i-k1);\r
1267                                         }\r
1268                                 }\r
1269                                 n = k;\r
1270                                 while ((w&1)==0) {\r
1271                                         w >>= 1;\r
1272                                         --n;\r
1273                                 }\r
1274                                 if ((i -= n) <0) {\r
1275                                         i += DB;\r
1276                                         --j;\r
1277                                 }\r
1278                                 if (is1) { // ret == 1, don't bother squaring or multiplying it\r
1279                                         g[w].copyTo(r);\r
1280                                         is1 = false;\r
1281                                 } else {\r
1282                                         while (n>1) {\r
1283                                                 z.sqrTo(r, r2);\r
1284                                                 z.sqrTo(r2, r);\r
1285                                                 n -= 2;\r
1286                                         }\r
1287                                         if (n>0) {\r
1288                                                 z.sqrTo(r, r2);\r
1289                                         } else {\r
1290                                                 t = r;\r
1291                                                 r = r2;\r
1292                                                 r2 = t;\r
1293                                         }\r
1294                                         z.mulTo(r2, g[w], r);\r
1295                                 }\r
1296                                 while (j>=0 && (e.a[j]&(1<<i)) == 0) {\r
1297                                         z.sqrTo(r, r2);\r
1298                                         t = r;\r
1299                                         r = r2;\r
1300                                         r2 = t;\r
1301                                         if (--i<0) {\r
1302                                                 i = DB-1;\r
1303                                                 --j;\r
1304                                         }\r
1305                                         \r
1306                                 }\r
1307                         }\r
1308                         return z.revert(r);\r
1309                 }\r
1310                 \r
1311                 /**\r
1312                  * \r
1313                  * @param a\r
1314                  * @return gcd(this, a) (HAC 14.54)\r
1315                  * \r
1316                  */\r
1317                 public function gcd(a:BigInteger):BigInteger {\r
1318                         var x:BigInteger = (s<0)?negate():clone();\r
1319                         var y:BigInteger = (a.s<0)?a.negate():a.clone();\r
1320                         if (x.compareTo(y)<0) {\r
1321                                 var t:BigInteger=x;\r
1322                                 x=y;\r
1323                                 y=t;\r
1324                         }\r
1325                         var i:int = x.getLowestSetBit();\r
1326                         var g:int = y.getLowestSetBit();\r
1327                         if (g<0) return x;\r
1328                         if (i<g) g= i;\r
1329                         if (g>0) {\r
1330                                 x.rShiftTo(g, x);\r
1331                                 y.rShiftTo(g, y);\r
1332                         }\r
1333                         while (x.sigNum()>0) {\r
1334                                 if ((i = x.getLowestSetBit()) >0) {\r
1335                                         x.rShiftTo(i, x);\r
1336                                 }\r
1337                                 if ((i = y.getLowestSetBit()) >0) {\r
1338                                         y.rShiftTo(i, y);\r
1339                                 }\r
1340                                 if (x.compareTo(y) >= 0) {\r
1341                                         x.subTo(y, x);\r
1342                                         x.rShiftTo(1, x);\r
1343                                 } else {\r
1344                                         y.subTo(x, y);\r
1345                                         y.rShiftTo(1, y);\r
1346                                 }\r
1347                         }\r
1348                         if (g>0) {\r
1349                                 y.lShiftTo(g, y);\r
1350                         }\r
1351                         return y;\r
1352                 }\r
1353 \r
1354                 /**\r
1355                  * \r
1356                  * @param n\r
1357                  * @return this % n, n < 2^DB\r
1358                  * \r
1359                  */\r
1360                 protected function modInt(n:int):int {\r
1361                         if (n<=0) return 0;\r
1362                         var d:int = DV%n;\r
1363                         var r:int = (s<0)?n-1:0;\r
1364                         if (t>0) {\r
1365                                 if (d==0) {\r
1366                                         r = a[0]%n;\r
1367                                 } else {\r
1368                                         for (var i:int=t-1;i>=0;--i) {\r
1369                                                 r = (d*r+a[i])%n;\r
1370                                         }\r
1371                                 }\r
1372                         }\r
1373                         return r;\r
1374                 }\r
1375                 \r
1376                 /**\r
1377                  * \r
1378                  * @param m\r
1379                  * @return 1/this %m (HAC 14.61)\r
1380                  * \r
1381                  */\r
1382                 public function modInverse(m:BigInteger):BigInteger {\r
1383                         var ac:Boolean = m.isEven();\r
1384                         if ((isEven()&&ac) || m.sigNum()==0) {\r
1385                                 return BigInteger.ZERO;\r
1386                         }\r
1387                         var u:BigInteger = m.clone();\r
1388                         var v:BigInteger = clone();\r
1389                         var a:BigInteger = nbv(1);\r
1390                         var b:BigInteger = nbv(0);\r
1391                         var c:BigInteger = nbv(0);\r
1392                         var d:BigInteger = nbv(1);\r
1393                         while (u.sigNum()!=0) {\r
1394                                 while (u.isEven()) {\r
1395                                         u.rShiftTo(1,u);\r
1396                                         if (ac) {\r
1397                                                 if (!a.isEven() || !b.isEven()) {\r
1398                                                         a.addTo(this,a);\r
1399                                                         b.subTo(m,b);\r
1400                                                 }\r
1401                                                 a.rShiftTo(1,a);\r
1402                                         } else if (!b.isEven()) {\r
1403                                                 b.subTo(m,b);\r
1404                                         }\r
1405                                         b.rShiftTo(1,b);\r
1406                                 }\r
1407                                 while (v.isEven()) {\r
1408                                         v.rShiftTo(1,v);\r
1409                                         if (ac) {\r
1410                                                 if (!c.isEven() || !d.isEven()) {\r
1411                                                         c.addTo(this,c);\r
1412                                                         d.subTo(m,d);\r
1413                                                 }\r
1414                                                 c.rShiftTo(1,c);\r
1415                                         } else if (!d.isEven()) {\r
1416                                                 d.subTo(m,d);\r
1417                                         }\r
1418                                         d.rShiftTo(1,d);\r
1419                                 }\r
1420                                 if (u.compareTo(v)>=0) {\r
1421                                         u.subTo(v,u);\r
1422                                         if (ac) {\r
1423                                                 a.subTo(c,a);\r
1424                                         }\r
1425                                         b.subTo(d,b);\r
1426                                 } else {\r
1427                                         v.subTo(u,v);\r
1428                                         if (ac) {\r
1429                                                 c.subTo(a,c);\r
1430                                         }\r
1431                                         d.subTo(b,d);\r
1432                                 }\r
1433                         }\r
1434                         if (v.compareTo(BigInteger.ONE) != 0) {\r
1435                                 return BigInteger.ZERO;\r
1436                         }\r
1437                         if (d.compareTo(m) >= 0) {\r
1438                                 return d.subtract(m);\r
1439                         }\r
1440                         if (d.sigNum()<0) {\r
1441                                 d.addTo(m,d);\r
1442                         } else {\r
1443                                 return d;\r
1444                         }\r
1445                         if (d.sigNum()<0) {\r
1446                                 return d.add(m);\r
1447                         } else {\r
1448                                 return d;\r
1449                         }\r
1450                 }\r
1451 \r
1452                 /**\r
1453                  * \r
1454                  * @param t\r
1455                  * @return primality with certainty >= 1-.5^t\r
1456                  * \r
1457                  */\r
1458                 public function isProbablePrime(t:int):Boolean {\r
1459                         var i:int;\r
1460                         var x:BigInteger = abs();\r
1461                         if (x.t == 1 && x.a[0]<=lowprimes[lowprimes.length-1]) {\r
1462                                 for (i=0;i<lowprimes.length;++i) {\r
1463                                         if (x[0]==lowprimes[i]) return true;\r
1464                                 }\r
1465                                 return false;\r
1466                         }\r
1467                         if (x.isEven()) return false;\r
1468                         i = 1;\r
1469                         while (i<lowprimes.length) {\r
1470                                 var m:int = lowprimes[i];\r
1471                                 var j:int = i+1;\r
1472                                 while (j<lowprimes.length && m<lplim) {\r
1473                                         m *= lowprimes[j++];\r
1474                                 }\r
1475                                 m = x.modInt(m);\r
1476                                 while (i<j) {\r
1477                                         if (m%lowprimes[i++]==0) {\r
1478                                                 return false;\r
1479                                         }\r
1480                                 }\r
1481                         }\r
1482                         return x.millerRabin(t);\r
1483                 }\r
1484                 \r
1485                 /**\r
1486                  * \r
1487                  * @param t\r
1488                  * @return true if probably prime (HAC 4.24, Miller-Rabin)\r
1489                  * \r
1490                  */\r
1491                 protected function millerRabin(t:int):Boolean {\r
1492                         var n1:BigInteger = subtract(BigInteger.ONE);\r
1493                         var k:int = n1.getLowestSetBit();\r
1494                         if (k<=0) {\r
1495                                 return false;\r
1496                         }\r
1497                         var r:BigInteger = n1.shiftRight(k);\r
1498                         t = (t+1)>>1;\r
1499                         if (t>lowprimes.length) {\r
1500                                 t = lowprimes.length;\r
1501                         }\r
1502                         var a:BigInteger = new BigInteger;\r
1503                         for (var i:int=0;i<t;++i) {\r
1504                                 a.fromInt(lowprimes[i]);\r
1505                                 var y:BigInteger = a.modPow(r, this);\r
1506                                 if (y.compareTo(BigInteger.ONE)!=0 && y.compareTo(n1)!=0) {\r
1507                                         var j:int = 1;\r
1508                                         while (j++<k && y.compareTo(n1)!=0) {\r
1509                                                 y = y.modPowInt(2, this);\r
1510                                                 if (y.compareTo(BigInteger.ONE)==0) {\r
1511                                                         return false;\r
1512                                                 }\r
1513                                         }\r
1514                                         if (y.compareTo(n1)!=0) {\r
1515                                                 return false;\r
1516                                         }\r
1517                                 }\r
1518                         }\r
1519                         return true;\r
1520                 }\r
1521 \r
1522                 /**\r
1523                  * Tweak our BigInteger until it looks prime enough\r
1524                  * \r
1525                  * @param bits\r
1526                  * @param t\r
1527                  * \r
1528                  */\r
1529                 public function primify(bits:int, t:int):void {\r
1530                         if (!testBit(bits-1)) { // force MSB set\r
1531                                 bitwiseTo(BigInteger.ONE.shiftLeft(bits-1), op_or, this);\r
1532                         }\r
1533                         if (isEven()) {\r
1534                                 dAddOffset(1,0);        // force odd\r
1535                         }\r
1536                         while (!isProbablePrime(t)) {\r
1537                                 dAddOffset(2,0);\r
1538                                 while(bitLength()>bits) subTo(BigInteger.ONE.shiftLeft(bits-1),this);\r
1539                         }\r
1540                 }\r
1541 \r
1542         }\r
1543 }\r