package tezos-plonk

Represents a polynomial

Returns the polynomial P(X) = 0

Returns the polynomial P(X) = 1

Returns the degree of the polynomial

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

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}

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

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

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)

mult_by_scalar s P returns s*P(X)

is_null P returns true iff P(X) = 0

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

opposite P returns -P(X)

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

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.

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.

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

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

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

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

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.

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

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

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

Infix operator for equal

Infix operator for add

Infix operator for polynomial_multiplication

Infix operator for sub