feat: Rust product of extension field elements utilities.

[feltroidprime]

To compute multi pairings checks hints, we need to have a function that computes a product of extension field elements (the 12-degree extension) in the form of polynomials of degree 11, and store both the quotient Q and the remainder R, as polynomials.

Q can be of arbitrary degree, but R must of degree 11 (12 coefficients)

garaga/hydra/garaga/hints/extf_mul.py

Lines 17 to 45 in c344b09

	def nondeterministic_extension_field_mul_divmod(
	Ps: list[list[PyFelt | ModuloCircuitElement]],
	curve_id: int,
	extension_degree: int,
	) -> tuple[list[PyFelt], list[PyFelt]]:
	Ps = [Polynomial(P) for P in Ps]
	field = get_base_field(curve_id)
	P_irr = get_irreducible_poly(curve_id, extension_degree)
	z_poly = reduce(operator.mul, Ps) # Π(Pi)
	z_polyq, z_polyr = divmod(z_poly, P_irr)
	z_polyr_coeffs = z_polyr.get_coeffs()
	z_polyq_coeffs = z_polyq.get_coeffs()
	# assert len(z_polyq_coeffs) <= (
	# extension_degree - 1
	# ), f"len z_polyq_coeffs={len(z_polyq_coeffs)}, degree: {z_polyq.degree()}"
	assert (
	len(z_polyr_coeffs) <= extension_degree
	), f"len z_polyr_coeffs={len(z_polyr_coeffs)}, degree: {z_polyr.degree()}"
	# Extend polynomials with 0 coefficients to match the expected lengths.
	# TODO : pass exact expected max degree when len(Ps)>2.
	z_polyq_coeffs += [field(0)] * (extension_degree - 1 - len(z_polyq_coeffs))
	z_polyr_coeffs += [field(0)] * (extension_degree - len(z_polyr_coeffs))
	return (z_polyq_coeffs, z_polyr_coeffs)

Implement an equivalent version of this function that works with polynomials in input and output., parametrized by <F> (or Polynomial<F>), although it should work only for BN and BLS.

They key is that this function takes a list of Polynomial<F> as input, and returns Q, R, two polynomials such that they correspond to the euclidean division of the product of the input by some constant Polynomial parametrized by <F>

The constant polynomials are defined in definitions.py. Only use the degree-12 one.

To perform the computation, polynomial.rs has the necessary methods, especially divmod.