polynomialExponentiationMod static method

List<BigInt> polynomialExponentiationMod(List<BigInt> base, BigInt exponent, List<BigInt> polymod, BigInt p,)

Computes the modular exponentiation of a polynomial represented by base to the power of exponent, using the specified polymod and modulus p.

Implementation

static List<BigInt> polynomialExponentiationMod(
    List<BigInt> base, BigInt exponent, List<BigInt> polymod, BigInt p) {
  assert(exponent < p);

  if (exponent == BigInt.zero) {
    return [BigInt.one];
  }

  List<BigInt> G = List.from(base);
  BigInt k = exponent;
  List<BigInt> s =
      (k % BigInt.two == BigInt.one) ? List.from(G) : [BigInt.one];

  while (k > BigInt.one) {
    k = k ~/ BigInt.two;
    G = polynomialMultiplyMod(G, G, polymod, p);
    if (k % BigInt.two == BigInt.one) {
      s = polynomialMultiplyMod(G, s, polymod, p);
    }
  }

  return s;
}