API tools faq
paste
Advertisement
Guest User

Untitled

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