Module S.Polynomial This library implements polynomials of Bls12_381.Fr as arrays of contiguous memory in C, allowing much better performances for algorithms that scan the polynomials.
An array a of size n represents the polynomial $\sum_i^(n-1) ai X^i$ The length of a is always greater or equal than the degree+1 of its corresponding polynomial, if greater it padded with zeros. As a consequence a polynomial has many representations, namely all arrays with trailing zeros.
val init : int -> (int -> scalar ) -> t init n f returns a fresh polynomial of length n, with element number i initialized to the result of f i.
allocate len creates a zero polynomial of size len
erase p overwrites a polynomial p with a zero polynomial of the same size as the polynomial p
val generate_biased_random_polynomial : int -> t generate_biased_random_polynomial n generates a random polynomial of degree strictly lower than n, the distribution is NOT uniform, it is biased towards sparse polynomials and particularly towards the zero polynomial
random n generates a uniformly sampled polynomial among the set of all polynomials of degree strictly lower than n
degree p returns the degree of a polynomial p. Returns -1 for the zero polynomial
get p i returns the i-th element of a given array p, a coefficient of X^i in p
val to_string : t -> to_string p returns the string representation of a polynomial p
copy p returns a copy of a polynomial p
val truncate : len :int -> t -> t truncate ~len p returns a new polynomial made of the first len coefficients of p. If degree p + 1 is less than len then copy p is returned.
val to_dense_coefficients : t -> scalar arrayto_dense_coefficients p returns the dense representation of a polynomial p, i.e., it converts a C array to an OCaml array
of_dense p creates a value of type t from the dense representation of a polynomial p, i.e., it converts an OCaml array to a C array
val of_coefficients : (scalar * int) list-> t of_coefficients p creates a value of type t from the sparse representation of a polynomial p, i.e., it converts an OCaml array to a C array
val equal : t -> t -> equal a b checks whether a polynomial a is equal to a polynomial b
is_zero p checks whether a polynomial p is the zero polynomial
zero is the zero polynomial, the neutral element for polynomial addition
one is the constant polynomial one, the neutral element for polynomial multiplication
add computes polynomial addition
val add_inplace : t -> t -> t -> add_inplace res a b computes polynomial addition of a and b and writes the result in res
Note: res can be equal to either a or b
sub computes polynomial subtraction
val sub_inplace : t -> t -> t -> sub_inplace res a b computes polynomial subtraction of a and b and writes the result in res
Note: res can be equal to either a or b
mul computes polynomial multiplication
Note: naive quadratic algorithm, result's size is the sum of arguments' size
mul_by_scalar computes multiplication of a polynomial by a blst_fr element
val mul_by_scalar_inplace : t -> scalar -> t -> mul_by_scalar_inplace res s p computes multiplication of a polynomial p by a blst_fr element s and stores it in res
linear p s computes ∑ᵢ s.(i)·p.(i)
val linear_with_powers : t list-> scalar -> t linear_with_powers p s computes ∑ᵢ sⁱ·p.(i). This function is more efficient than linear + powers
opposite computes polynomial negation
val opposite_inplace : t -> opposite_inplace p computes polynomial negation
Note: The argument p is overwritten
evaluate p x evaluates a polynomial p at x
exception Rest_not_null of stringval division_xn : t -> int -> scalar -> t * t division_xn p n c returns the quotient and remainder of the division of p by (X^n + c)
mul_xn p n c returns the product of p and (X^n + c)
derivative p returns the formal derivative of p
val split : nb_chunks :int -> int -> t -> t listval blind : nb_blinds :int -> int -> t -> t * t blind ~nb_blinds n p adds to polynomial p a random multiple of polynomial (X^n - 1), chosen by uniformly sampling a polynomial b of degree strictly lower than nb_blinds and multiplying it by (X^n - 1), b is returned as the second argument
constant s creates a value of type t from a blst_fr element s
val fold_left_map : ('acc -> scalar -> 'acc * scalar ) -> 'acc -> t -> 'acc * t fold_left_map is a combination of fold_left and map that threads an accumulator through calls to f.