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.

This function efficiently calculates (base^exponent) % polymod, where base, polymod, and p are all polynomials with coefficients represented as BigInt. The result is also a polynomial with coefficients mod p.

The function iteratively squares and multiplies the base polynomial using the exponent to achieve the modular exponentiation.

• base: The base polynomial.
• exponent: The non-negative exponent.
• polymod: The modulus polynomial.
• p: The modulus value.

Returns the polynomial resulting from (base^exponent) % polymod.

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;
}