1 package com.hurlant.math

     2 {

     3 	use namespace bi_internal;

     4 	/**

     5 	 * Montgomery reduction

     6 	 */

     7 	internal class MontgomeryReduction implements IReduction

     8 	{

     9 		private var m:BigInteger;

    10 		private var mp:int;

    11 		private var mpl:int;

    12 		private var mph:int;

    13 		private var um:int;

    14 		private var mt2:int;

    15 		public function MontgomeryReduction(m:BigInteger) {

    16 			this.m = m;

    17 			mp = m.invDigit();

    18 			mpl = mp & 0x7fff;

    19 			mph = mp>>15;

    20 			um = (1<<(BigInteger.DB-15))-1;

    21 			mt2 = 2*m.t;

    22 		}

    23 		/**

    24 		 * xR mod m

    25 		 */

    26 		public function convert(x:BigInteger):BigInteger {

    27 			var r:BigInteger = new BigInteger;

    28 		 	x.abs().dlShiftTo(m.t, r);

    29 		 	r.divRemTo(m, null, r);

    30 		 	if (x.s<0 && r.compareTo(BigInteger.ZERO)>0) {

    31 		 		m.subTo(r,r);

    32 		 	}

    33 		 	return r;

    34 		}

    35 		/**

    36 		 * x/R mod m

    37 		 */

    38 		public function revert(x:BigInteger):BigInteger {

    39 			var r:BigInteger = new BigInteger;

    40 			x.copyTo(r);

    41 			reduce(r);

    42 			return r;

    43 		}

    44 		/**

    45 		 * x = x/R mod m (HAC 14.32)

    46 		 */

    47 		public function reduce(x:BigInteger):void {

    48 			while (x.t<=mt2) {		// pad x so am has enough room later

    49 				x.a[x.t++] = 0;

    50 			}

    51 			for (var i:int=0; i<m.t; ++i) {

    52 				// faster way of calculating u0 = x[i]*mp mod DV

    53 				var j:int = x.a[i]&0x7fff;

    54 				var u0:int = (j*mpl+(((j*mph+(x.a[i]>>15)*mpl)&um)<<15))&BigInteger.DM;

    55 				// use am to combine the multiply-shift-add into one call

    56 				j = i+m.t;

    57 				x.a[j] += m.am(0, u0, x, i, 0, m.t);

    58 				// propagate carry

    59 				while (x.a[j]>=BigInteger.DV) {

    60 					x.a[j] -= BigInteger.DV;

    61 					x.a[++j]++;

    62 				}

    63 			}

    64 	 		x.clamp();

    65 		 	x.drShiftTo(m.t, x);

    66 	 		if (x.compareTo(m)>=0) {

    67 	 			x.subTo(m,x);

    68 	 		}

    69 		}

    70 		/**

    71 		 * r = "x^2/R mod m"; x != r

    72 		 */

    73 		public function sqrTo(x:BigInteger, r:BigInteger):void {

    74 			x.squareTo(r);

    75 			reduce(r);

    76 		}

    77 		/**

    78 		 * r = "xy/R mod m"; x,y != r

    79 		 */

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

    81 			x.multiplyTo(y,r);

    82 			reduce(r);

    83 		}

    84 	}

    85 }