package octez-bls12-381-polynomial

  1. Overview
  2. Docs
type fr = Fr.t
type fr_array = Fr_carray.t
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 disjoint
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 -> log_degree:int -> unit

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)
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 Domain.Stubs.compute_domain)
val dft_inplace : fr_array -> fr_array -> bool -> int -> unit

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)
val fft_prime_factor_algorithm_inplace : fr_array -> (fr_array * int) -> (fr_array * int) -> bool -> unit

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

Innovation. Community. Security.