package tezos-plonk

  1. Overview
  2. Docs
Legend:
Library
Module
Module type
Parameter
Class
Class type
type t
type polynomial = t

Represents a polynomial

val zero : polynomial

Returns the polynomial P(X) = 0

val one : polynomial

Returns the polynomial P(X) = 1

Returns the degree of the polynomial

val degree_int : polynomial -> int
val have_same_degree : polynomial -> polynomial -> bool

have_same_degree P Q returns true if P and Q have the same degree

val get_dense_polynomial_coefficients : polynomial -> scalar list

get_dense_polynomial_coeffiecients P returns the list of the coefficients of P, including the null coefficients, in decreasing order i.e. if P(X) = a_

  1. a_

    X + ... + a_n - 1 X^n - 1, the function will return a_{n - 1}, ..., a_{0}

val get_dense_polynomial_coefficients_with_degree : polynomial -> (scalar * int) list
val get_list_coefficients : polynomial -> (scalar * int) list

get_list_coefficients P returns (a_4,4), (a_2,2), (a_0,0) if P = a_4 X^4 + a_2 X^2 + a_0

val evaluation : polynomial -> scalar -> scalar

evaluation P s computes P(s). Use Horner's method in O(n).

val constants : scalar -> polynomial

constants s returns the constant polynomial P(X) = s

add P Q returns P(X) + Q(X)

sub P Q returns P(X) - Q(X)

val mult_by_scalar : scalar -> polynomial -> polynomial

mult_by_scalar s P returns s*P(X)

val is_null : polynomial -> bool

is_null P returns true iff P(X) = 0

val is_constant : polynomial -> bool

is_constant P returns true iff P(X) = s for s scalar

val opposite : polynomial -> polynomial

opposite P returns -P(X)

val equal : polynomial -> polynomial -> bool

equal P Q returns true iff P(X) = Q(X) on S

val of_coefficients : (scalar * int) list -> polynomial

of_coefficients [(x_0, y_0) ; (x_1, y_1); ... ; (x_n ; y_n)] builds the polynomial Σ(a_i * X^i) as a type polynomial.

By default, the null coefficients will be removed as the internal representation of polynomials is sparsed. However, a version with null coefficients can be generated if required. It is not recommended to use this possibility as it breaks an invariant of the type polynomial.

val lagrange_interpolation : (scalar * scalar) list -> polynomial

lagrange_interpolation [(x_0, y_0) ; (x_1, y_1); ... ; (x_n ; y_n)] builds the unique polynomial P of degre n such that P(x_i) = y_i for i = 0...n using the intermediate lagrange polynomials. lagrange_interpolation_fft can be used in case of a FFT friendly scalar structure. It is supposed all x_i are different.

val even_polynomial : polynomial -> polynomial

even_polynomial P returns the polynomial P_even containing only the even coefficients of P

val odd_polynomial : polynomial -> polynomial

odd_polynomial P returns the polynomial P_odd containing only the odd coefficients of P

val evaluation_fft : domain:scalar array -> polynomial -> scalar list

evaluate_fft ~domain P evaluates P on the points given in the domain. The domain should be of the form g^{i} where g is a principal root of unity. If the domain is of size n, g must be a n-th principal root of unity. The degree of P can be smaller than the domain size, but not larger. The complexity is in O(n log(m)) where n is the domain size and m the degree of the polynomial. The resulting list contains the evaluation points P(1), P(w), ..., P(w^{n - 1}).

generate_random_polynomial n returns a random polynomial of degree n

val get_highest_coefficient : polynomial -> scalar

get_highest_coefficient P where P(X) = a_n X^n + ... a_0 returns a_n

val interpolation_fft : domain:scalar array -> scalar list -> polynomial

interpolation_fft ~domain [y_{0} ; y_{1} ; ... y_{n}] computes the interpolation at the points y_{0}, ..., y_{n} using FFT Cookey Tukey. The domain should be of the form g^{i} where g is a principal root of unity. If the domain is of size n, g must be a n-th principal root of unity. The domain size must be exactly the same than the number of points. The complexity is O(n log(n)) where n is the domain size.

val polynomial_multiplication : polynomial -> polynomial -> polynomial

polynomial_multiplication P Q computes the product P(X).Q(X)

val polynomial_multiplication_fft : domain:scalar array -> polynomial -> polynomial -> polynomial

polynomial_multiplication_fft ~domain P Q computes the product P(X).Q(X) using FFT. The domain should be of the form g^{i} where g is a principal root of unity. If the domain is of size n, g must be a n-th principal root of unity. The degrees of P and Q can be different. The only condition is degree P + degree Q should be smaller or equal to n - 2 (i.e. the domain should be big enough to compute n - 1 points of P * Q).

val euclidian_division_opt : polynomial -> polynomial -> (polynomial * polynomial) option
val extended_euclide : polynomial -> polynomial -> polynomial * polynomial * polynomial

extended_euclide P S returns (GCD, U, V) the greatest common divisor of P and S and the Bezout's coefficient: U P + V S = GCD and GCD greatest coefficient is one

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

Infix operator for equal

Infix operator for add

Infix operator for polynomial_multiplication

Infix operator for sub

val to_string : polynomial -> string
OCaml

Innovation. Community. Security.