tezos-bls12-381-polynomial 0.1.0

type fr = Polynomial_c.Stubs.fr

type fr_array = Polynomial_c.Stubs.fr_array

val add : fr_array -> fr_array -> fr_array -> int -> int -> unit

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

val mul_arrays : 
  fr_array ->
  (fr_array * int * int * Stdlib.Bytes.t * int) array ->
  int ->
  int ->
  unit

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 either pairwise disjoint or equal when cᵢ = 0

val linear_arrays : 
  fr_array ->
  (fr_array * int * fr * int) array ->
  fr ->
  int ->
  int ->
  unit

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

val fft_inplace : 
  fr_array ->
  domain:fr_array ->
  log:int ->
  degree:int ->
  log_degree:int ->
  unit

fft_inplace p domain log 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 compute_domain)

val ifft_inplace : fr_array -> domain:fr_array -> log:int -> unit

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 compute_domain)

package tezos-bls12-381-polynomial