|
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);
}
}
}
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
I currently hold the following qualifications (amongst others, I also studied Music Technology and Electronics, for my sins)
- MSc (Passed with distinctions), in Information Technology for E-Commerce
- BSc Hons (1st class) in Computer Science & Artificial Intelligence
Both of these at Sussex University UK.
Award(s)
I am lucky enough to have won a few awards for Zany Crazy code articles over the years
- Microsoft C# MVP 2016
- Codeproject MVP 2016
- Microsoft C# MVP 2015
- Codeproject MVP 2015
- Microsoft C# MVP 2014
- Codeproject MVP 2014
- Microsoft C# MVP 2013
- Codeproject MVP 2013
- Microsoft C# MVP 2012
- Codeproject MVP 2012
- Microsoft C# MVP 2011
- Codeproject MVP 2011
- Microsoft C# MVP 2010
- Codeproject MVP 2010
- Microsoft C# MVP 2009
- Codeproject MVP 2009
- Microsoft C# MVP 2008
- Codeproject MVP 2008
- And numerous codeproject awards which you can see over at my blog