package octez-bls12-381-polynomial

add res a b size_a size_b writes the result of polynomial addition of a and b using the evaluation representation in res, where

• a is evaluated on domain_a of size size_a
• b is evaluated on domain_b of size size_b

requires:

• size a = size_a
• size b = size_b
• size res = min (size_a, size_b)
• res, a and b are either pairwise disjoint or equal
• size_b mod size_a = 0

mul_arrays res eval_evallen_comp_power_powlen size_res nb_evals writes the result of computing p₁(gᶜ₁·x)ᵐ₁·p₂(gᶜ₂·x)ᵐ₂·…·pₖ(gᶜₖ·x)ᵐₖ using the evaluation representation in res, where

• eval_evallen_comp_power_powlen.[i] = (pᵢ, size_p_i, cᵢ, mᵢ, size_bits_m_i)
• a polynomial pᵢ is evaluated on domain_p_i of size size_p_i
• cᵢ is a composition_gx; it computes pᵢ(gᶜᵢ·x) instead of pᵢ(x), where g is a primitive size_p_i-th root of unity
• mᵢ is a power in pᵢ(x)ᵐᵢ
• size_bits_m_i is the *exact* number of bits in mᵢ
• nb_evals is a number of evaluations, i.e., i = 1..nb_evals

requires:

• size res = size_res
• size eval_evallen_comp_power_powlen = nb_evals
• size p_i = size_p_i
• size_bits m_i = size_bits_m_i
• size_p_i mod size_res = 0
• res and p_i are disjoint

linear_arrays res eval_evallen_coeff_comp add_constant size_res nb_evals writes the result of computing λ₁·p₁(gᶜ₁·x) + λ₂·p₂(gᶜ₂·x) + … + λₖ·pₖ(gᶜₖ·x) + add_constant using the evaluation representation in res, where

• eval_evallen_coeff_comp.[i] = (pᵢ, size_p_i, λᵢ, cᵢ)
• a polynomial pᵢ is evaluated on domain_p_i of size size_p_i
• cᵢ is a composition_gx; it computes pᵢ(gᶜᵢ·x) instead of pᵢ(x), where g is a primitive size_p_i-th root of unity
• λᵢ is a coefficient in λᵢ·pᵢ(x)
• nb_evals is a number of evaluations, i.e., i = 1..nb_evals

requires:

• size res = size_res
• size eval_evallen_coeff_comp = nb_evals
• size p_i = size_p_i
• size_p_i mod size_res = 0
• res and p_i are disjoint

fft_inplace p domain log log_degree computes Fast Fourier Transform. It converts the coefficient representation of a polynomial p to the evaluation representation

requires:

• size p = size domain
• size domain = 2^log
• domain = [one; g; ..; g^{n-1}] where g is a primitive n-th root of unity and n = 2^log (as done by Domain.Stubs.compute_domain)

ifft_inplace p domain log computes Inverse Fast Fourier Transform. It converts the evaluation representation of a polynomial p to the coefficient representation

requires:

• size p = size domain
• size domain = 2^log
• domain = [one; g; ..; g^{n-1}] where g is a primitive n-th root of unity and n = 2^log (as done by Domain.Stubs.compute_domain)

dft_inplace coefficients domain inverse length computes the Fourier Transform.

requires:

• size domain = size coefficients = length
• length <= 2^10
• length != 2^k
• if inverse = true then the inverse dft is performed
• domain = [one; g; ..; g^{n-1}] where g is a primitive n-th root of unity (as done by Domain.Stubs.compute_domain)

fft_prime_factor_algorithm_inplace coefficient (domain1, domain1_length) (domain2, domain2_length) inverse computes the Fast Fourier Transform following the Prime-factor FFT algorithm.

requires:

• size domain1 = domain1_length
• size domain2 = domain2_length
• size domain1 and size domain2 to be coprime
• if for some k size domain1 != 2^k then size domain1 <= 2^10
• if for some k size domain2 != 2^k then size domain2 <= 2^10
• size coefficients = domain1_length * domain2_length
• if inverse = true then the inverse fft is performed
• domain = [one; g; ..; g^{n-1}] where g is a primitive n-th root of unity (as done by Domain.Stubs.compute_domain)