polynomialReduceMod static method

List<BigInt> polynomialReduceMod(List<BigInt> poly, List<BigInt> polymod, BigInt p)

Reduce a polynomial 'poly' modulo 'polymod' using prime 'p'.

Implementation

static List<BigInt> polynomialReduceMod(
    List<BigInt> poly, List<BigInt> polymod, BigInt p) {
  assert(polymod.last == BigInt.one);
  assert(polymod.length > 1);

  // Repeatedly reduce the polynomial while its degree is greater than or equal to 'polymod':
  while (poly.length >= polymod.length) {
    if (poly.last != BigInt.zero) {
      for (int i = 2; i <= polymod.length; i++) {
        poly[poly.length - i] = (poly[poly.length - i] -
                poly.last * polymod[polymod.length - i]) %
            p;
      }
    }
    poly.removeLast();
  }

  return poly;
}