Barrett Class / solvr:bignum Library / Dart Documentation

Barrett Class

Barrett modular reduction

Constructors

Code new Barrett(BigInteger m) #

Barrett modular reduction

Barrett(this.m) {
  // setup Barrett
  this.r2 = BigInteger.nbi();
  this.q3 = BigInteger.nbi();
  BigInteger.ONE.dlShiftTo(2*m.t,this.r2);
  this.mu = this.r2.divide(m);
  
}

Methods

Code BigInteger convert(BigInteger x) #

BigInteger convert(BigInteger x) {
  if(x.s < 0 || x.t > 2*this.m.t)  {
    return x.mod(this.m);
  } else if(x.compareTo(this.m) < 0) { 
    return x;
  } else { 
    var r = BigInteger.nbi(); 
    x.copyTo(r); 
    this.reduce(r); 
    return r;  
  }
}

Code mulTo(x, y, r) #

r = x*y mod m; x,y != r

mulTo(x,y,r) { x.multiplyTo(y,r); this.reduce(r); }

Code void reduce(BigInteger x) #

x = x mod m (HAC 14.42)

void reduce(BigInteger x) {
  x.drShiftTo(this.m.t - 1, this.r2);
  if(x.t > this.m.t+1) { 
    x.t = this.m.t+1; 
    x.clamp();   
  }
  
  this.mu.multiplyUpperTo(this.r2, this.m.t + 1, this.q3);
  this.m.multiplyLowerTo(this.q3, this.m.t + 1, this.r2);
  while(x.compareTo(this.r2) < 0) { 
    x.dAddOffset(1,this.m.t+1);
  }
  
  x.subTo(this.r2,x);
  
  while(x.compareTo(this.m) >= 0) { 
    x.subTo(this.m,x);
  }
}

Code revert(x) #

revert(x) { 
  return x;   
}

Code sqrTo(x, r) #

r = x^2 mod m; x != r

sqrTo(x,r) { x.squareTo(r); this.reduce(r); }

Fields

Code BigInteger m #

BigInteger m;

Code var mu #

var mu;

Code BigInteger q3 #

BigInteger q3;

Code BigInteger r2 #

BigInteger r2;