polynomialMultiplyMod static method

List<BigInt> polynomialMultiplyMod(
  1. List<BigInt> m1,
  2. List<BigInt> m2,
  3. List<BigInt> polymod,
  4. BigInt p,
)

Multiply two polynomials represented by lists 'm1' and 'm2', reducing modulo 'polymod' and prime 'p'.

Implementation

static List<BigInt> polynomialMultiplyMod(
    List<BigInt> m1, List<BigInt> m2, List<BigInt> polymod, BigInt p) {
  final List<BigInt> prod =
      List.filled(m1.length + m2.length - 1, BigInt.zero);

  // Add together all the cross-terms:
  for (int i = 0; i < m1.length; i++) {
    for (int j = 0; j < m2.length; j++) {
      prod[i + j] = (prod[i + j] + m1[i] * m2[j]) % p;
    }
  }

  // Reduce the result modulo 'polymod':
  return polynomialReduceMod(prod, polymod, p);
}