package octez-libs

  1. Overview
  2. Docs
package octez-libs
Legend:
Library
Module
Module type
Parameter
Class
Class type

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.

type scalar = scalar
type t
val t : t Repr.t
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.

val allocate : int -> t

allocate len creates a zero polynomial of size len

val erase : t -> unit

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

val random : int -> t

random n generates a uniformly sampled polynomial among the set of all polynomials of degree strictly lower than n

val degree : t -> int

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

val get : t -> int -> scalar

get p i returns the i-th element of a given array p, a coefficient of X^i in p

val to_string : t -> string

to_string p returns the string representation of a polynomial p

val copy : t -> t

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.

  • raises [Invalid_argument]

    if len is negative.

val to_dense_coefficients : t -> scalar array

to_dense_coefficients p returns the dense representation of a polynomial p, i.e., it converts a C array to an OCaml array

val of_dense : scalar array -> t

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 -> bool

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

val is_zero : t -> bool

is_zero p checks whether a polynomial p is the zero polynomial

val zero : t

zero is the zero polynomial, the neutral element for polynomial addition

val one : t

one is the constant polynomial one, the neutral element for polynomial multiplication

val add : t -> t -> t

add computes polynomial addition

val add_inplace : t -> t -> t -> unit

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

val sub : t -> t -> t

sub computes polynomial subtraction

val sub_inplace : t -> t -> t -> unit

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

val mul : t -> t -> t

mul computes polynomial multiplication

Note: naive quadratic algorithm, result's size is the sum of arguments' size

val mul_by_scalar : scalar -> t -> t

mul_by_scalar computes multiplication of a polynomial by a blst_fr element

val mul_by_scalar_inplace : t -> scalar -> t -> unit

mul_by_scalar_inplace res s p computes multiplication of a polynomial p by a blst_fr element s and stores it in res

val linear : t list -> scalar list -> t

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

val opposite : t -> t

opposite computes polynomial negation

val opposite_inplace : t -> unit

opposite_inplace p computes polynomial negation

Note: The argument p is overwritten

val evaluate : t -> scalar -> scalar

evaluate p x evaluates a polynomial p at x

exception Rest_not_null of string
val 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)

val mul_xn : t -> int -> scalar -> t

mul_xn p n c returns the product of p and (X^n + c)

val derivative : t -> t

derivative p returns the formal derivative of p

val split : nb_chunks:int -> int -> t -> t list
val 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

val (=) : t -> t -> bool

Infix operator for equal

val (+) : t -> t -> t

Infix operator for add

val (-) : t -> t -> t

Infix operator for sub

val (*) : t -> t -> t

Infix operator for mul

val constant : scalar -> t

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.

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct