package com.hurlant.math

{

	use namespace bi_internal;

	/**

	 * Montgomery reduction

	 */

	internal class MontgomeryReduction implements IReduction

	{

		private var m:BigInteger;

		private var mp:int;

		private var mpl:int;

		private var mph:int;

		private var um:int;

		private var mt2:int;

		public function MontgomeryReduction(m:BigInteger) {

			this.m = m;

			mp = m.invDigit();

			mpl = mp & 0x7fff;

			mph = mp>>15;

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

			mt2 = 2*m.t;

		}

		/**

		 * xR mod m

		 */

		public function convert(x:BigInteger):BigInteger {

			var r:BigInteger = new BigInteger;

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

		 	r.divRemTo(m, null, r);

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

		 		m.subTo(r,r);

		 	}

		 	return r;

		}

		/**

		 * x/R mod m

		 */

		public function revert(x:BigInteger):BigInteger {

			var r:BigInteger = new BigInteger;

			x.copyTo(r);

			reduce(r);

			return r;

		}

		/**

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

		 */

		public function reduce(x:BigInteger):void {

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

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

			}

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

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

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

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

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

				j = i+m.t;

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

				// propagate carry

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

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

					x.a[++j]++;

				}

			}

	 		x.clamp();

		 	x.drShiftTo(m.t, x);

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

	 			x.subTo(m,x);

	 		}

		}

		/**

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

		 */

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

			x.squareTo(r);

			reduce(r);

		}

		/**

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

		 */

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

			x.multiplyTo(y,r);

			reduce(r);

		}

	}

}