1 /**

     2  * BigInteger

     3  * 

     4  * An ActionScript 3 implementation of BigInteger (light version)

     5  * Copyright (c) 2007 Henri Torgemane

     6  * 

     7  * Derived from:

     8  * 		The jsbn library, Copyright (c) 2003-2005 Tom Wu

     9  * 

    10  * See LICENSE.txt for full license information.

    11  */

    12 package com.hurlant.math

    13 {

    14 

    15 	import com.hurlant.crypto.prng.Random;

    16 	import com.hurlant.util.Hex;

    17 	import com.hurlant.util.Memory;

    18 	

    19 	import flash.utils.ByteArray;

    20 	use namespace bi_internal;

    21 

    22 	public class BigInteger

    23 	{

    24 		public static const DB:int = 30; // number of significant bits per chunk

    25 		public static const DV:int = (1<<DB);

    26 		public static const DM:int = (DV-1); // Max value in a chunk

    27 		

    28 		public static const BI_FP:int = 52;

    29 		public static const FV:Number = Math.pow(2, BI_FP);

    30 		public static const F1:int = BI_FP - DB;

    31 		public static const F2:int = 2*DB - BI_FP;

    32 		

    33 		public static const ZERO:BigInteger = nbv(0);

    34 		public static const ONE:BigInteger  = nbv(1);

    35 		

    36 		/*bi_internal */public var t:int; // number of chunks.

    37 		bi_internal var s:int; // sign

    38 		bi_internal var a:Array; // chunks

    39 		

    40 		/**

    41 		 * 

    42 		 * @param value

    43 		 * @param radix  WARNING: If value is ByteArray, this holds the number of bytes to use.

    44 		 * @param unsigned

    45 		 * 

    46 		 */

    47 		public function BigInteger(value:* = null, radix:int = 0, unsigned:Boolean = false) {

    48 			a = new Array;

    49 			if (value is String) {

    50 				if (radix&&radix!=16) throw new Error("BigInteger construction with radix!=16 is not supported.");

    51 				value = Hex.toArray(value);

    52 				radix=0;

    53 			}

    54 			if (value is ByteArray) {

    55 				var array:ByteArray = value as ByteArray;

    56 				var length:int = radix || (array.length - array.position);

    57 				fromArray(array, length, unsigned);

    58 			}

    59 		}

    60 		public function dispose():void {

    61 			var r:Random = new Random;

    62 			for (var i:uint=0;i<a.length;i++) {

    63 				a[i] = r.nextByte();

    64 				delete a[i];

    65 			}

    66 			a=null;

    67 			t=0;

    68 			s=0;

    69 			Memory.gc();

    70 		}

    71 		

    72 		public function toString(radix:Number=16):String {

    73 			if (s<0) return "-"+negate().toString(radix);

    74 			var k:int;

    75 			switch (radix) {

    76 				case 2:   k=1; break;

    77 				case 4:   k=2; break;

    78 				case 8:   k=3; break;

    79 				case 16:  k=4; break;

    80 				case 32:  k=5; break;

    81 				default:

    82 //					return toRadix(radix);

    83 			}

    84 			var km:int = (1<<k)-1;

    85 			var d:int = 0;

    86 			var m:Boolean = false;

    87 			var r:String = "";

    88 			var i:int = t;

    89 			var p:int = DB-(i*DB)%k;

    90 			if (i-->0) {

    91 				if (p<DB && (d=a[i]>>p)>0) {

    92 					m = true;

    93 					r = d.toString(36);

    94 				}

    95 				while (i >= 0) {

    96 					if (p<k) {

    97 						d = (a[i]&((1<<p)-1))<<(k-p);

    98 						d|= a[--i]>>(p+=DB-k);

    99 					} else {

   100 						d = (a[i]>>(p-=k))&km;

   101 						if (p<=0) {

   102 							p += DB;

   103 							--i;

   104 						}

   105 					}

   106 					if (d>0) {

   107 						m = true;

   108 					}

   109 					if (m) {

   110 						r += d.toString(36);

   111 					}

   112 				}

   113 			}

   114 			return m?r:"0";

   115 		}

   116 		public function toArray(array:ByteArray):uint {

   117 			const k:int = 8;

   118 			const km:int = (1<<8)-1;

   119 			var d:int = 0;

   120 			var i:int = t;

   121 			var p:int = DB-(i*DB)%k;

   122 			var m:Boolean = false;

   123 			var c:int = 0;

   124 			if (i-->0) {

   125 				if (p<DB && (d=a[i]>>p)>0) {

   126 					m = true;

   127 					array.writeByte(d);

   128 					c++;

   129 				}

   130 				while (i >= 0) {

   131 					if (p<k) {

   132 						d = (a[i]&((1<<p)-1))<<(k-p);

   133 						d|= a[--i]>>(p+=DB-k);

   134 					} else {

   135 						d = (a[i]>>(p-=k))&km;

   136 						if (p<=0) {

   137 							p += DB;

   138 							--i;

   139 						}

   140 					}

   141 					if (d>0) {

   142 						m = true;

   143 					}

   144 					if (m) {

   145 						array.writeByte(d);

   146 						c++;

   147 					}

   148 				}

   149 			}

   150 			return c;

   151 		}

   152 		/**

   153 		 * best-effort attempt to fit into a Number.

   154 		 * precision can be lost if it just can't fit.

   155 		 */

   156 		public function valueOf():Number {

   157 			if (s==-1) {

   158 				return -negate().valueOf();

   159 			}

   160 			var coef:Number = 1;

   161 			var value:Number = 0;

   162 			for (var i:uint=0;i<t;i++) {

   163 				value += a[i]*coef;

   164 				coef *= DV;

   165 			}

   166 			return value;

   167 		}

   168 		/**

   169 		 * -this

   170 		 */

   171 		public function negate():BigInteger {

   172 			var r:BigInteger = nbi();

   173 			ZERO.subTo(this, r);

   174 			return r;

   175 		}

   176 		/**

   177 		 * |this|

   178 		 */

   179 		public function abs():BigInteger {

   180 			return (s<0)?negate():this;

   181 		}

   182 		/**

   183 		 * return + if this > v, - if this < v, 0 if equal

   184 		 */

   185 		public function compareTo(v:BigInteger):int {

   186 			var r:int = s - v.s;

   187 			if (r!=0) {

   188 				return r;

   189 			}

   190 			var i:int = t;

   191 			r = i-v.t;

   192 			if (r!=0) {

   193 				return r;

   194 			}

   195 			while (--i >=0) {

   196 				r=a[i]-v.a[i];

   197 				if (r != 0) return r;

   198 			}

   199 			return 0;

   200 		}

   201 		/**

   202 		 * returns bit length of the integer x

   203 		 */

   204 		bi_internal function nbits(x:int):int {

   205 			var r:int = 1;

   206 			var t:int;

   207 			if ((t=x>>>16) != 0) { x = t; r += 16; }

   208 			if ((t=x>>8) != 0) { x = t; r += 8; }

   209 			if ((t=x>>4) != 0) { x = t; r += 4; }

   210 			if ((t=x>>2) != 0) { x = t; r += 2; }

   211 			if ((t=x>>1) != 0) { x = t; r += 1; }

   212 			return r;

   213 		}

   214 		/**

   215 		 * returns the number of bits in this

   216 		 */

   217 		public function bitLength():int {

   218 			if (t<=0) return 0;

   219 			return DB*(t-1)+nbits(a[t-1]^(s&DM));

   220 		}

   221 		/**

   222 		 * 

   223 		 * @param v

   224 		 * @return this % v

   225 		 * 

   226 		 */

   227 		public function mod(v:BigInteger):BigInteger {

   228 			var r:BigInteger = nbi();

   229 			abs().divRemTo(v,null,r);

   230 			if (s<0 && r.compareTo(ZERO)>0) {

   231 				v.subTo(r,r);

   232 			}

   233 			return r;

   234 		}

   235 		/**

   236 		 * this^e % m, 0 <= e < 2^32

   237 		 */

   238 		public function modPowInt(e:int, m:BigInteger):BigInteger {

   239 			var z:IReduction;

   240 			if (e<256 || m.isEven()) {

   241 				z = new ClassicReduction(m);

   242 			} else {

   243 				z = new MontgomeryReduction(m);

   244 			}

   245 			return exp(e, z);

   246 		}

   247 

   248 		/**

   249 		 * copy this to r

   250 		 */

   251 		bi_internal function copyTo(r:BigInteger):void {

   252 			for (var i:int = t-1; i>=0; --i) {

   253 				r.a[i] = a[i];

   254 			}

   255 			r.t = t;

   256 			r.s = s;

   257 		}

   258 		/**

   259 		 * set from integer value "value", -DV <= value < DV

   260 		 */

   261 		bi_internal function fromInt(value:int):void {

   262 			t = 1;

   263 			s = (value<0)?-1:0;

   264 			if (value>0) {

   265 				a[0] = value;

   266 			} else if (value<-1) {

   267 				a[0] = value+DV;

   268 			} else {

   269 				t = 0;

   270 			}

   271 		}

   272 		/**

   273 		 * set from ByteArray and length,

   274 		 * starting a current position

   275 		 * If length goes beyond the array, pad with zeroes.

   276 		 */

   277 		bi_internal function fromArray(value:ByteArray, length:int, unsigned:Boolean = false):void {

   278 			var p:int = value.position;

   279 			var i:int = p+length;

   280 			var sh:int = 0;

   281 			const k:int = 8;

   282 			t = 0;

   283 			s = 0;

   284 			while (--i >= p) {

   285 				var x:int = i<value.length?value[i]:0;

   286 				if (sh == 0) {

   287 					a[t++] = x;

   288 				} else if (sh+k > DB) {

   289 					a[t-1] |= (x&((1<<(DB-sh))-1))<<sh;

   290 					a[t++] = x>>(DB-sh);

   291 				} else {

   292 					a[t-1] |= x<<sh;

   293 				}

   294 				sh += k;

   295 				if (sh >= DB) sh -= DB;

   296 			}

   297 			if (!unsigned && (value[0]&0x80)==0x80) {

   298 				s = -1;

   299 				if (sh > 0) {

   300 					a[t-1] |= ((1<<(DB-sh))-1)<<sh;

   301 				}

   302 			}

   303 			clamp();

   304 			value.position = Math.min(p+length,value.length);

   305 		}

   306 		/**

   307 		 * clamp off excess high words

   308 		 */

   309 		bi_internal function clamp():void {

   310 			var c:int = s&DM;

   311 			while (t>0 && a[t-1]==c) {

   312 				--t;

   313 			}

   314 		}

   315 		/**

   316 		 * r = this << n*DB

   317 		 */

   318 		bi_internal function dlShiftTo(n:int, r:BigInteger):void {

   319 			var i:int;

   320 			for (i=t-1; i>=0; --i) {

   321 				r.a[i+n] = a[i];

   322 			}

   323 			for (i=n-1; i>=0; --i) {

   324 				r.a[i] = 0;

   325 			}

   326 			r.t = t+n;

   327 			r.s = s;

   328 		}

   329 		/**

   330 		 * r = this >> n*DB

   331 		 */

   332 		bi_internal function drShiftTo(n:int, r:BigInteger):void {

   333 			var i:int;

   334 			for (i=n; i<t; ++i) {

   335 				r.a[i-n] = a[i];

   336 			}

   337 			r.t = Math.max(t-n,0);

   338 			r.s = s;

   339 		}

   340 		/**

   341 		 * r = this << n

   342 		 */

   343 		bi_internal function lShiftTo(n:int, r:BigInteger):void {

   344 			var bs:int = n%DB;

   345 			var cbs:int = DB-bs;

   346 			var bm:int = (1<<cbs)-1;

   347 			var ds:int = n/DB;

   348 			var c:int = (s<<bs)&DM;

   349 			var i:int;

   350 			for (i=t-1; i>=0; --i) {

   351 				r.a[i+ds+1] = (a[i]>>cbs)|c;

   352 				c = (a[i]&bm)<<bs;

   353 			}

   354 			for (i=ds-1; i>=0; --i) {

   355 				r.a[i] = 0;

   356 			}

   357 			r.a[ds] = c;

   358 			r.t = t+ds+1;

   359 			r.s = s;

   360 			r.clamp();

   361 		}

   362 		/**

   363 		 * r = this >> n

   364 		 */

   365 		bi_internal function rShiftTo(n:int, r:BigInteger):void {

   366 			r.s = s;

   367 			var ds:int = n/DB;

   368 			if (ds >= t) {

   369 				r.t = 0;

   370 				return;

   371 			}

   372 			var bs:int = n%DB;

   373 			var cbs:int = DB-bs;

   374 			var bm:int = (1<<bs)-1;

   375 			r.a[0] = a[ds]>>bs;

   376 			var i:int;

   377 			for (i=ds+1; i<t; ++i) {

   378 				r.a[i-ds-1] |= (a[i]&bm)<<cbs;

   379 				r.a[i-ds] = a[i]>>bs;

   380 			}

   381 			if (bs>0) {

   382 				r.a[t-ds-1] |= (s&bm)<<cbs;

   383 			}

   384 			r.t = t-ds;

   385 			r.clamp();

   386 		}

   387 		/**

   388 		 * r = this - v

   389 		 */

   390 		bi_internal function subTo(v:BigInteger, r:BigInteger):void {

   391 			var i:int = 0;

   392 			var c:int = 0;

   393 			var m:int = Math.min(v.t, t);

   394 			while (i<m) {

   395 				c += a[i] - v.a[i];

   396 				r.a[i++] = c & DM;

   397 				c >>= DB;

   398 			}

   399 			if (v.t < t) {

   400 				c -= v.s;

   401 				while (i< t) {

   402 					c+= a[i];

   403 					r.a[i++] = c&DM;

   404 					c >>= DB;

   405 				}

   406 				c += s;

   407 			} else {

   408 				c += s;

   409 				while (i < v.t) {

   410 					c -= v.a[i];

   411 					r.a[i++] = c&DM;

   412 					c >>= DB;

   413 				}

   414 				c -= v.s;

   415 			}

   416 			r.s = (c<0)?-1:0;

   417 			if (c<-1) {

   418 				r.a[i++] = DV+c;

   419 			} else if (c>0) {

   420 				r.a[i++] = c;

   421 			}

   422 			r.t = i;

   423 			r.clamp();

   424 		}

   425 		/**

   426 		 * am: Compute w_j += (x*this_i), propagates carries,

   427 		 * c is initial carry, returns final carry.

   428 		 * c < 3*dvalue, x < 2*dvalue, this_i < dvalue

   429 		 */

   430 		bi_internal function am(i:int,x:int,w:BigInteger,j:int,c:int,n:int):int {

   431 			var xl:int = x&0x7fff;

   432 			var xh:int = x>>15;

   433 			while(--n >= 0) {

   434 				var l:int = a[i]&0x7fff;

   435 				var h:int = a[i++]>>15;

   436 				var m:int = xh*l + h*xl;

   437 				l = xl*l + ((m&0x7fff)<<15)+w.a[j]+(c&0x3fffffff);

   438 				c = (l>>>30)+(m>>>15)+xh*h+(c>>>30);

   439 				w.a[j++] = l&0x3fffffff;

   440 			}

   441 			return c;

   442 		}

   443 		/**

   444 		 * r = this * v, r != this,a (HAC 14.12)

   445 		 * "this" should be the larger one if appropriate

   446 		 */

   447 		bi_internal function multiplyTo(v:BigInteger, r:BigInteger):void {

   448 			var x:BigInteger = abs();

   449 			var y:BigInteger = v.abs();

   450 			var i:int = x.t;

   451 			r.t = i+y.t;

   452 			while (--i >= 0) {

   453 				r.a[i] = 0;

   454 			}

   455 			for (i=0; i<y.t; ++i) {

   456 				r.a[i+x.t] = x.am(0, y.a[i], r, i, 0, x.t);

   457 			}

   458 			r.s = 0;

   459 			r.clamp();

   460 			if (s!=v.s) {

   461 				ZERO.subTo(r, r);

   462 			}

   463 		}

   464 		/**

   465 		 * r = this^2, r != this (HAC 14.16)

   466 		 */

   467 		bi_internal function squareTo(r:BigInteger):void {

   468 			var x:BigInteger = abs();

   469 			var i:int = r.t = 2*x.t;

   470 			while (--i>=0) r.a[i] = 0;

   471 			for (i=0; i<x.t-1; ++i) {

   472 				var c:int = x.am(i, x.a[i], r, 2*i, 0, 1);

   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) {

   474 					r.a[i+x.t] -= DV;

   475 					r.a[i+x.t+1] = 1;

   476 				}

   477 			}

   478 			if (r.t>0) {

   479 				r.a[r.t-1] += x.am(i, x.a[i], r, 2*i, 0, 1);

   480 			}

   481 			r.s = 0;

   482 			r.clamp();

   483 		}

   484 		/**

   485 		 * divide this by m, quotient and remainder to q, r (HAC 14.20)

   486 		 * r != q, this != m. q or r may be null.

   487 		 */

   488 		bi_internal function divRemTo(m:BigInteger, q:BigInteger = null, r:BigInteger = null):void {

   489 			var pm:BigInteger = m.abs();

   490 			if (pm.t <= 0) return;

   491 			var pt:BigInteger = abs();

   492 			if (pt.t < pm.t) {

   493 				if (q!=null) q.fromInt(0);

   494 				if (r!=null) copyTo(r);

   495 				return;

   496 			}

   497 			if (r==null) r = nbi();

   498 			var y:BigInteger = nbi();

   499 			var ts:int = s;

   500 			var ms:int = m.s;

   501 			var nsh:int = DB-nbits(pm.a[pm.t-1]); // normalize modulus

   502 			if (nsh>0) {

   503 				pm.lShiftTo(nsh, y);

   504 				pt.lShiftTo(nsh, r);

   505 			} else {

   506 				pm.copyTo(y);

   507 				pt.copyTo(r);

   508 			}

   509 			var ys:int = y.t;

   510 			var y0:int = y.a[ys-1];

   511 			if (y0==0) return;

   512 			var yt:Number = y0*(1<<F1)+((ys>1)?y.a[ys-2]>>F2:0);

   513 			var d1:Number = FV/yt;

   514 			var d2:Number = (1<<F1)/yt;

   515 			var e:Number = 1<<F2;

   516 			var i:int = r.t;

   517 			var j:int = i-ys;

   518 			var t:BigInteger = (q==null)?nbi():q;

   519 			y.dlShiftTo(j,t);

   520 			if (r.compareTo(t)>=0) {

   521 				r.a[r.t++] = 1;

   522 				r.subTo(t,r);

   523 			}

   524 			ONE.dlShiftTo(ys,t);

   525 			t.subTo(y,y); // "negative" y so we can replace sub with am later.

   526 			while(y.t<ys) y.(y.t++, 0);

   527 			while(--j >= 0) {

   528 				// Estimate quotient digit

   529 				var qd:int = (r.a[--i]==y0)?DM:Number(r.a[i])*d1+(Number(r.a[i-1])+e)*d2;

   530 				if ((r.a[i]+= y.am(0, qd, r, j, 0, ys))<qd) { // Try it out

   531 					y.dlShiftTo(j, t);

   532 					r.subTo(t,r);

   533 					while (r.a[i]<--qd) {

   534 						r.subTo(t,r);

   535 					}

   536 				}

   537 			}

   538 			if (q!=null) {

   539 				r.drShiftTo(ys,q);

   540 				if (ts!=ms) {

   541 					ZERO.subTo(q,q);

   542 				}

   543 			}

   544 			r.t = ys;

   545 			r.clamp();

   546 			if (nsh>0) {

   547 				r.rShiftTo(nsh, r); // Denormalize remainder

   548 			}

   549 			if (ts<0) {

   550 				ZERO.subTo(r,r);

   551 			}

   552 		}

   553 		/**

   554 		 * return "-1/this % 2^DB"; useful for Mont. reduction

   555 		 * justification:

   556 		 *         xy == 1 (mod n)

   557 		 *         xy =  1+km

   558 		 * 	 xy(2-xy) = (1+km)(1-km)

   559 		 * x[y(2-xy)] =  1-k^2.m^2

   560 		 * x[y(2-xy)] == 1 (mod m^2)

   561 		 * if y is 1/x mod m, then y(2-xy) is 1/x mod m^2

   562 		 * should reduce x and y(2-xy) by m^2 at each step to keep size bounded

   563 		 * [XXX unit test the living shit out of this.]

   564 		 */

   565 		bi_internal function invDigit():int {

   566 			if (t<1) return 0;

   567 			var x:int = a[0];

   568 			if ((x&1)==0) return 0;

   569 			var y:int = x&3; 							// y == 1/x mod 2^2

   570 			y = (y*(2-(x&0xf )*y))             &0xf;	// y == 1/x mod 2^4

   571 			y = (y*(2-(x&0xff)*y))             &0xff;	// y == 1/x mod 2^8

   572 			y = (y*(2-(((x&0xffff)*y)&0xffff)))&0xffff;	// y == 1/x mod 2^16

   573 			// last step - calculate inverse mod DV directly;

   574 			// assumes 16 < DB <= 32 and assumes ability to handle 48-bit ints

   575 			// XXX 48 bit ints? Whaaaa? is there an implicit float conversion in here?

   576 			y = (y*(2-x*y%DV))%DV;	// y == 1/x mod 2^dbits

   577 			// we really want the negative inverse, and -DV < y < DV

   578 			return (y>0)?DV-y:-y;

   579 		}

   580 		/**

   581 		 * true iff this is even

   582 		 */

   583 		bi_internal function isEven():Boolean {

   584 			return ((t>0)?(a[0]&1):s) == 0;

   585 		}

   586 		/**

   587 		 * this^e, e < 2^32, doing sqr and mul with "r" (HAC 14.79)

   588 		 */

   589 		bi_internal function exp(e:int, z:IReduction):BigInteger {

   590 			if (e > 0xffffffff || e < 1) return ONE;

   591 			var r:BigInteger = nbi();

   592 			var r2:BigInteger = nbi();

   593 			var g:BigInteger = z.convert(this);

   594 			var i:int = nbits(e)-1;

   595 			g.copyTo(r);

   596 			while(--i>=0) {

   597 				z.sqrTo(r, r2);

   598 				if ((e&(1<<i))>0) {

   599 					z.mulTo(r2,g,r);

   600 				} else {

   601 					var t:BigInteger = r;

   602 					r = r2;

   603 					r2 = t;

   604 				}

   605 				

   606 			}

   607 			return z.revert(r);

   608 		}

   609 		bi_internal function intAt(str:String, index:int):int {

   610 			return parseInt(str.charAt(index), 36);

   611 		}

   612 

   613 

   614 		protected function nbi():* {

   615 			return new BigInteger;

   616 		}

   617 		/**

   618 		 * return bigint initialized to value

   619 		 */

   620 		public static function nbv(value:int):BigInteger {

   621 			var bn:BigInteger = new BigInteger;

   622 			bn.fromInt(value);

   623 			return bn;

   624 		}

   625 

   626 

   627 		// Functions above are sufficient for RSA encryption.

   628 		// The stuff below is useful for decryption and key generation

   629 

   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];

   631 		public static const lplim:int = (1<<26)/lowprimes[lowprimes.length-1];

   632 

   633 

   634 		public function clone():BigInteger {

   635 			var r:BigInteger = new BigInteger;

   636 			this.copyTo(r);

   637 			return r;

   638 		}

   639 		

   640 		/**

   641 		 * 

   642 		 * @return value as integer

   643 		 * 

   644 		 */

   645 		public function intValue():int {

   646 			if (s<0) {

   647 				if (t==1) {

   648 					return a[0]-DV;

   649 				} else if (t==0) {

   650 					return -1;

   651 				}

   652 			} else if (t==1) {

   653 				return a[0];

   654 			} else if (t==0) {

   655 				return 0;

   656 			}

   657 			// assumes 16 < DB < 32

   658 			return  ((a[1]&((1<<(32-DB))-1))<<DB)|a[0];

   659 		}

   660 		

   661 		/**

   662 		 * 

   663 		 * @return value as byte

   664 		 * 

   665 		 */

   666 		public function byteValue():int {

   667 			return (t==0)?s:(a[0]<<24)>>24;

   668 		}

   669 		

   670 		/**

   671 		 * 

   672 		 * @return value as short (assumes DB>=16)

   673 		 * 

   674 		 */

   675 		public function shortValue():int {

   676 			return (t==0)?s:(a[0]<<16)>>16;

   677 		}

   678 		

   679 		/**

   680 		 * 

   681 		 * @param r

   682 		 * @return x s.t. r^x < DV

   683 		 * 

   684 		 */

   685 		protected function chunkSize(r:Number):int {

   686 			return Math.floor(Math.LN2*DB/Math.log(r));

   687 		}

   688 		

   689 		/**

   690 		 * 

   691 		 * @return 0 if this ==0, 1 if this >0

   692 		 * 

   693 		 */

   694 		public function sigNum():int {

   695 			if (s<0) {

   696 				return -1;

   697 			} else if (t<=0 || (t==1 && a[0]<=0)) {

   698 				return 0;

   699 			} else{

   700 				return 1;

   701 			}

   702 		}

   703 		

   704 		/**

   705 		 * 

   706 		 * @param b: radix to use

   707 		 * @return a string representing the integer converted to the radix.

   708 		 * 

   709 		 */

   710 		protected function toRadix(b:uint=10):String {

   711 			if (sigNum()==0 || b<2 || b>32) return "0";

   712 			var cs:int = chunkSize(b);

   713 			var a:Number = Math.pow(b, cs);

   714 			var d:BigInteger = nbv(a);

   715 			var y:BigInteger = nbi();

   716 			var z:BigInteger = nbi();

   717 			var r:String = "";

   718 			divRemTo(d, y, z);

   719 			while (y.sigNum()>0) {

   720 				r = (a+z.intValue()).toString(b).substr(1) + r;

   721 				y.divRemTo(d,y,z);

   722 			}

   723 			return z.intValue().toString(b) + r;

   724 		}

   725 		

   726 		/**

   727 		 * 

   728 		 * @param s a string to convert from using radix.

   729 		 * @param b a radix

   730 		 * 

   731 		 */

   732 		protected function fromRadix(s:String, b:int = 10):void {

   733 			fromInt(0);

   734 			var cs:int = chunkSize(b);

   735 			var d:Number = Math.pow(b, cs);

   736 			var mi:Boolean = false;

   737 			var j:int = 0;

   738 			var w:int = 0;

   739 			for (var i:int=0;i<s.length;++i) {

   740 				var x:int = intAt(s, i);

   741 				if (x<0) {

   742 					if (s.charAt(i) == "-" && sigNum() == 0) {

   743 						mi = true;

   744 					}

   745 					continue;

   746 				}

   747 				w = b*w+x;

   748 				if (++j >= cs) {

   749 					dMultiply(d);

   750 					dAddOffset(w,0);

   751 					j=0;

   752 					w=0;

   753 				}

   754 			}

   755 			if (j>0) {

   756 				dMultiply(Math.pow(b,j));

   757 				dAddOffset(w,0);

   758 			}

   759 			if (mi) {

   760 				BigInteger.ZERO.subTo(this, this);

   761 			}

   762 		}

   763 		

   764 		// XXX function fromNumber not written yet.

   765 		

   766 		/**

   767 		 * 

   768 		 * @return a byte array.

   769 		 * 

   770 		 */

   771 		public function toByteArray():ByteArray {

   772 			var i:int = t;

   773 			var r:ByteArray = new ByteArray;

   774 			r[0] = s;

   775 			var p:int = DB-(i*DB)%8;

   776 			var d:int;

   777 			var k:int=0;

   778 			if (i-->0) {

   779 				if (p<DB && (d=a[i]>>p)!=(s&DM)>>p) {

   780 					r[k++] = d|(s<<(DB-p));

   781 				}

   782 				while (i>=0) {

   783 					if(p<8) {

   784 						d = (a[i]&((1<<p)-1))<<(8-p);

   785 						d|= a[--i]>>(p+=DB-8);

   786 					} else {

   787 						d = (a[i]>>(p-=8))&0xff;

   788 						if (p<=0) {

   789 							p += DB;

   790 							--i;

   791 						}

   792 					}

   793 					if ((d&0x80)!=0) d|=-256;

   794 					if (k==0 && (s&0x80)!=(d&0x80)) ++k;

   795 					if (k>0 || d!=s) r[k++] = d;

   796 				} 

   797 			}

   798 			return r;

   799 		}

   800 

   801 		public function equals(a:BigInteger):Boolean {

   802 			return compareTo(a)==0;

   803 		}

   804 		public function min(a:BigInteger):BigInteger {

   805 			return (compareTo(a)<0)?this:a;

   806 		}

   807 		public function max(a:BigInteger):BigInteger {

   808 			return (compareTo(a)>0)?this:a;

   809 		}

   810 		

   811 		/**

   812 		 * 

   813 		 * @param a	a BigInteger to perform the operation with

   814 		 * @param op a Function implementing the operation

   815 		 * @param r a BigInteger to store the result of the operation

   816 		 * 

   817 		 */

   818 		protected function bitwiseTo(a:BigInteger, op:Function, r:BigInteger):void {

   819 			var i:int;

   820 			var f:int;

   821 			var m:int = Math.min(a.t, t);

   822 			for (i=0; i<m; ++i) {

   823 				r.a[i] = op(this.a[i],a.a[i]);

   824 			}

   825 			if (a.t<t) {

   826 				f = a.s&DM;

   827 				for (i=m;i<t;++i) {

   828 					r.a[i] = op(this.a[i],f);

   829 				}

   830 				r.t = t;

   831 			} else {

   832 				f = s&DM;

   833 				for (i=m;i<a.t;++i) {

   834 					r.a[i] = op(f,a.a[i]);

   835 				}

   836 				r.t = a.t;

   837 			}

   838 			r.s = op(s, a.s);

   839 			r.clamp();

   840 		}

   841 		

   842 		private function op_and(x:int, y:int):int {return x&y;}

   843 		public function and(a:BigInteger):BigInteger {

   844 			var r:BigInteger = new BigInteger;

   845 			bitwiseTo(a, op_and, r);

   846 			return r;

   847 		}

   848 		

   849 		private function op_or(x:int, y:int):int {return x|y;}

   850 		public function or(a:BigInteger):BigInteger {

   851 			var r:BigInteger = new BigInteger;

   852 			bitwiseTo(a, op_or, r);

   853 			return r;

   854 		}

   855 		

   856 		private function op_xor(x:int, y:int):int {return x^y;}

   857 		public function xor(a:BigInteger):BigInteger {

   858 			var r:BigInteger = new BigInteger;

   859 			bitwiseTo(a, op_xor, r);

   860 			return r;

   861 		}

   862 		

   863 		private function op_andnot(x:int, y:int):int { return x&~y;}

   864 		public function andNot(a:BigInteger):BigInteger {

   865 			var r:BigInteger = new BigInteger;

   866 			bitwiseTo(a, op_andnot, r);

   867 			return r;

   868 		}

   869 		

   870 		public function not():BigInteger {

   871 			var r:BigInteger = new BigInteger;

   872 			for (var i:int=0;i<t;++i) {

   873 				r[i] = DM&~a[i];

   874 			}

   875 			r.t = t;

   876 			r.s = ~s;

   877 			return r;

   878 		}

   879 		

   880 		public function shiftLeft(n:int):BigInteger {

   881 			var r:BigInteger = new BigInteger;

   882 			if (n<0) {

   883 				rShiftTo(-n, r);

   884 			} else {

   885 				lShiftTo(n, r);

   886 			}

   887 			return r;

   888 		}

   889 		public function shiftRight(n:int):BigInteger {

   890 			var r:BigInteger = new BigInteger;

   891 			if (n<0) {

   892 				lShiftTo(-n, r);

   893 			} else {

   894 				rShiftTo(n, r);

   895 			}

   896 			return r;

   897 		}

   898 		

   899 		/**

   900 		 * 

   901 		 * @param x

   902 		 * @return index of lowet 1-bit in x, x < 2^31

   903 		 * 

   904 		 */

   905 		private function lbit(x:int):int {

   906 			if (x==0) return -1;

   907 			var r:int = 0;

   908 			if ((x&0xffff)==0) { x>>= 16; r += 16; }

   909 			if ((x&0xff) == 0) { x>>=  8; r +=  8; }

   910 			if ((x&0xf)  == 0) { x>>=  4; r +=  4; }

   911 			if ((x&0x3)  == 0) { x>>=  2; r +=  2; }

   912 			if ((x&0x1)  == 0) ++r;

   913 			return r;

   914 		}

   915 		

   916 		/**

   917 		 * 

   918 		 * @return index of lowest 1-bit (or -1 if none)

   919 		 * 

   920 		 */

   921 		public function getLowestSetBit():int {

   922 			for (var i:int=0;i<t;++i) {

   923 				if (a[i]!=0) return i*DB+lbit(a[i]);

   924 			}

   925 			if (s<0) return t*DB;

   926 			return -1;

   927 		}

   928 		

   929 		/**

   930 		 * 

   931 		 * @param x

   932 		 * @return number of 1 bits in x

   933 		 * 

   934 		 */

   935 		private function cbit(x:int):int {

   936 			var r:uint =0;

   937 			while (x!=0) { x &= x-1; ++r }

   938 			return r;

   939 		}

   940 		

   941 		/**

   942 		 * 

   943 		 * @return number of set bits

   944 		 * 

   945 		 */

   946 		public function bitCount():int {

   947 			var r:int=0;

   948 			var x:int = s&DM;

   949 			for (var i:int=0;i<t;++i) {

   950 				r += cbit(a[i]^x);

   951 			}

   952 			return r;

   953 		}

   954 		

   955 		/**

   956 		 * 

   957 		 * @param n

   958 		 * @return true iff nth bit is set

   959 		 * 

   960 		 */

   961 		public function testBit(n:int):Boolean {

   962 			var j:int = Math.floor(n/DB);

   963 			if (j>=t) {

   964 				return s!=0;

   965 			}

   966 			return ((a[j]&(1<<(n%DB)))!=0);

   967 		}

   968 		

   969 		/**

   970 		 * 

   971 		 * @param n

   972 		 * @param op

   973 		 * @return this op (1<<n)

   974 		 * 

   975 		 */

   976 		protected function changeBit(n:int,op:Function):BigInteger {

   977 			var r:BigInteger = BigInteger.ONE.shiftLeft(n);

   978 			bitwiseTo(r, op, r);

   979 			return r;

   980 		}

   981 		

   982 		/**

   983 		 * 

   984 		 * @param n

   985 		 * @return this | (1<<n)

   986 		 * 

   987 		 */

   988 		public function setBit(n:int):BigInteger { return changeBit(n, op_or); }

   989 

   990 		/**

   991 		 * 

   992 		 * @param n

   993 		 * @return this & ~(1<<n)

   994 		 * 

   995 		 */

   996 		public function clearBit(n:int):BigInteger { return changeBit(n, op_andnot); }

   997 

   998 		/**

   999 		 * 

  1000 		 * @param n

  1001 		 * @return this ^ (1<<n)

  1002 		 * 

  1003 		 */

  1004 		public function flipBit(n:int):BigInteger { return changeBit(n, op_xor); }

  1005 

  1006 		/**

  1007 		 * 

  1008 		 * @param a

  1009 		 * @param r = this + a

  1010 		 * 

  1011 		 */

  1012 		protected function addTo(a:BigInteger, r:BigInteger):void {

  1013 			var i:int = 0;

  1014 			var c:int = 0;

  1015 			var m:int = Math.min(a.t, t);

  1016 			while (i<m) {

  1017 				c += this.a[i] + a.a[i];

  1018 				r.a[i++] = c&DM;

  1019 				c>>=DB;

  1020 			}

  1021 			if (a.t < t) {

  1022 				c += a.s;

  1023 				while (i<t) {

  1024 					c += this.a[i];

  1025 					r.a[i++] = c&DM;

  1026 					c >>= DB;

  1027 				}

  1028 				c += s;

  1029 			} else {

  1030 				c += s;

  1031 				while (i<a.t) {

  1032 					c += a.a[i];

  1033 					r.a[i++] = c&DM;

  1034 					c >>= DB;

  1035 				}

  1036 				c += a.s;

  1037 			}

  1038 			r.s = (c<0)?-1:0;

  1039 			if (c>0) {

  1040 				r.a[i++] = c;

  1041 			} else if (c<-1) {

  1042 				r.a[i++] = DV+c;

  1043 			}

  1044 			r.t = i;

  1045 			r.clamp();

  1046 		}

  1047 		

  1048 		/**

  1049 		 * 

  1050 		 * @param a

  1051 		 * @return this + a

  1052 		 * 

  1053 		 */

  1054 		public function add(a:BigInteger):BigInteger {

  1055 			var r:BigInteger = new BigInteger;

  1056 			addTo(a,r);

  1057 			return r;

  1058 		}

  1059 

  1060 		/**

  1061 		 * 

  1062 		 * @param a

  1063 		 * @return this - a

  1064 		 * 

  1065 		 */

  1066 		public function subtract(a:BigInteger):BigInteger {

  1067 			var r:BigInteger = new BigInteger;

  1068 			subTo(a,r);

  1069 			return r;

  1070 		}

  1071 		

  1072 		/**

  1073 		 * 

  1074 		 * @param a

  1075 		 * @return this * a

  1076 		 * 

  1077 		 */

  1078 		public function multiply(a:BigInteger):BigInteger {

  1079 			var r:BigInteger = new BigInteger;

  1080 			multiplyTo(a,r);

  1081 			return r;

  1082 		}

  1083 		

  1084 		/**

  1085 		 * 

  1086 		 * @param a

  1087 		 * @return this / a

  1088 		 * 

  1089 		 */

  1090 		public function divide(a:BigInteger):BigInteger {

  1091 			var r:BigInteger = new BigInteger;

  1092 			divRemTo(a, r, null);

  1093 			return r;

  1094 		}

  1095 		

  1096 		public function remainder(a:BigInteger):BigInteger {

  1097 			var r:BigInteger = new BigInteger;

  1098 			divRemTo(a, null, r);

  1099 			return r;

  1100 		}

  1101 		

  1102 		/**

  1103 		 * 

  1104 		 * @param a

  1105 		 * @return [this/a, this%a]

  1106 		 * 

  1107 		 */

  1108 		public function divideAndRemainder(a:BigInteger):Array {

  1109 			var q:BigInteger = new BigInteger;

  1110 			var r:BigInteger = new BigInteger;

  1111 			divRemTo(a, q, r);

  1112 			return [q,r];

  1113 		}

  1114 		

  1115 		/**

  1116 		 * 

  1117 		 * this *= n, this >=0, 1 < n < DV

  1118 		 * 

  1119 		 * @param n

  1120 		 * 

  1121 		 */

  1122 		bi_internal function dMultiply(n:int):void {

  1123 			a[t] = am(0, n-1, this, 0, 0, t);

  1124 			++t;

  1125 			clamp();

  1126 		}

  1127 		

  1128 		/**

  1129 		 * 

  1130 		 * this += n << w words, this >= 0

  1131 		 * 

  1132 		 * @param n

  1133 		 * @param w

  1134 		 *