1 package com.hurlant.math

     2 {

     3 	use namespace bi_internal;

     4 

     5 	internal class BarrettReduction implements IReduction

     6 	{

     7 		private var m:BigInteger;

     8 		private var r2:BigInteger;

     9 		private var q3:BigInteger;

    10 		private var mu:BigInteger;

    11 		

    12 		public function BarrettReduction(m:BigInteger) {

    13 			// setup Barrett

    14 			r2 = new BigInteger;

    15 			q3 = new BigInteger;

    16 			BigInteger.ONE.dlShiftTo(2*m.t, r2);

    17 			mu = r2.divide(m);

    18 			this.m = m;

    19 		}

    20 		

    21 		public function revert(x:BigInteger):BigInteger

    22 		{

    23 			return x;

    24 		}

    25 		

    26 		/**

    27 		 * 

    28 		 * @param x

    29 		 * @param y

    30 		 * @param r = x*y mod m; x != r

    31 		 * 

    32 		 */

    33 		public function mulTo(x:BigInteger, y:BigInteger, r:BigInteger):void

    34 		{

    35 			x.multiplyTo(y, r);

    36 			reduce(r);

    37 		}

    38 		

    39 		/**

    40 		 * 

    41 		 * @param x

    42 		 * @param r = x^2 mod m; x != r

    43 		 * 

    44 		 */

    45 		public function sqrTo(x:BigInteger, r:BigInteger):void

    46 		{

    47 			x.squareTo(r);

    48 			reduce(r);

    49 		}

    50 		

    51 		public function convert(x:BigInteger):BigInteger

    52 		{

    53 			if (x.s<0 || x.t>2*m.t) {

    54 				return x.mod(m);

    55 			} else if (x.compareTo(m)<0) {

    56 				return x;

    57 			} else {

    58 				var r:BigInteger = new BigInteger;

    59 				x.copyTo(r);

    60 				reduce(r);

    61 				return r;

    62 			}

    63 		}

    64 		

    65 		/**

    66 		 * 

    67 		 * @param x = x mod m (HAC 14.42)

    68 		 * 

    69 		 */

    70 		public function reduce(lx:BigInteger):void

    71 		{

    72 			var x:BigInteger = lx as BigInteger;

    73 			x.drShiftTo(m.t-1,r2);

    74 			if (x.t>m.t+1) {

    75 				x.t = m.t+1;

    76 				x.clamp();

    77 			}

    78 			mu.multiplyUpperTo(r2, m.t+1, q3);

    79 			m.multiplyLowerTo(q3, m.t+1, r2);

    80 			while (x.compareTo(r2)<0) {

    81 				x.dAddOffset(1, m.t+1);

    82 			}

    83 			x.subTo(r2,x);

    84 			while (x.compareTo(m)>=0) {

    85 				x.subTo(m,x);

    86 			}

    87 		}

    88 		

    89 	}

    90 }