package octez-bls12-381-polynomial

init size f degree initializes an evaluation of a polynomial of the given degree.

of_array (d, e) creates a value of type t from the evaluation representation of a polynomial e of degree d, i.e, it converts an OCaml array to a C array

to_array converts a C array to an OCaml array

string_of_eval e returns the string representation of evaluation e

of_domain d converts d from type domain to type t.

Note: of_domain d doesn't create a copy of d

to_domain d converts d from type t to type domain.

Note: to_domain d doesn't create a copy of d

zero returns the evaluation representation of the zero polynomial

is_zero p checks whether a polynomial p is the zero polynomial

degree returns the degree of a polynomial. Returns -1 for the zero polynomial

length e returns the size of domain where a polynomial is evaluated, or equally, the size of a C array where evaluation e is stored

create len returns the evaluation representation of a zero polynomial of size len

copy ?res a returns a copy of evaluation a. The function writes the result in res if res has the correct size and allocates a new array for the result otherwise

get p i returns the i-th element of a given array p

get_inplace p i res copies the i-th element of a given array p in res

mul_by_scalar computes muliplication of a polynomial by a blst_fr element

mul_c computes p₁(gᶜ₁·x)ᵐ₁·p₂(gᶜ₂·x)ᵐ₂·…·pₖ(gᶜₖ·x)ᵐₖ, where

• pᵢ = List.nth evaluations i
• mᵢ = List.nth powers i
• cᵢ = List.nth (fst composition_gx) i
• n = snd composition_gx is the order of generator, i.e., gⁿ = 1

The function writes the result in res if res has the correct size (= min (size pᵢ)) and allocates a new array for the result otherwise

Note: res and pᵢ are disjoint

linear_c computes λ₁·p₁(gᶜ₁·x) + λ₂·p₂(gᶜ₂·x) + … + λₖ·pₖ(gᶜₖ·x) + add_constant, where

• pᵢ = List.nth evaluations i
• λᵢ = List.nth linear_coeffs i
• cᵢ = List.nth (fst composition_gx) i
• n = snd composition_gx is the order of generator, i.e., gⁿ = 1

The function writes the result in res if res has the correct size (= min (size pᵢ)) and allocates a new array for the result otherwise

Note: res and pᵢ are disjoint

linear_with_powers p s computes ∑ᵢ sⁱ·p.(i). This function is more efficient than linear + powers for evaluations of the same size

add ?res a b computes polynomial addition of a and b. The function writes the result in res if res has the correct size (= min (size (a, b))) and allocates a new array for the result otherwise

Note: res can be equal to either a or b

equal a b checks whether a polynomial a is equal to a polynomial b

Note: equal is defined as restrictive equality, i.e., the same polynomial evaluated on different domains are said to be different

evaluation_fft domain p converts the coefficient representation of a polynomial p to the evaluation representation. domain can be obtained using Domain.build

Note:

• size of domain must be a power of two
• degree of polynomial must be strictly less than the size of domain

interpolation_fft domain p converts the evaluation representation of a polynomial p to the coefficient representation. domain can be obtained using Domain.build

Note:

• size of domain must be a power of two
• size of a polynomial must be equal to size of domain

dft domain polynomial converts the coefficient representation of a polynomial p to the evaluation representation. domain can be obtained using Domain.build.

Computes the discrete Fourier transform in time O(n^2) where n = size domain.

requires:

• size domain to divide Bls12_381.Fr.order - 1
• size domain != 2^k
• degree polynomial < size domain

idft domain t converts the evaluation representation of a polynomial p to the coefficient representation. domain can be obtained using Domain.build.

Computes the inverse discrete Fourier transform in time O(n^2) where n = size domain.

requires:

• size domain to divide Bls12_381.Fr.order - 1
• size domain != 2^k
• size domain = size t

evaluation_fft_prime_factor_algorithm domain1 domain2 p converts the coefficient representation of a polynomial p to the evaluation representation. domain can be obtained using Domain.build. See the Prime-factor FFT algorithm.

requires:

• size domain1 * size domain2 to divide Bls12_381.Fr.order - 1
• 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
• degree polynomial < size domain1 * size domain2

interpolation_fft_prime_factor_algorithm domain1 domain2 t converts the evaluation representation of a polynomial p to the coefficient representation. domain can be obtained using Domain.build. See the Prime-factor FFT algorithm.

requires:

• size domain1 * size domain2 to divide Bls12_381.Fr.order - 1
• 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 t = size domain1 * size domain2