The type of the polynomial coefficients. Can be a field or more generally a ring. For the moment, it is restricted to prime fields.

Represents a polynomial

Returns the polynomial P(X) = 0

Returns the polynomial P(X) = 1

Returns the degree of the polynomial

degree_int P returns the degree of P as an integer. If P(X) = 0, returns -1

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) where -P(X) = -a_nX^n - a_(n - 1) X^(n - 1) - ... - a_0

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 ~generator:g ~power P evaluates P on the points {g^i} for i = 0...power. power must be a power of 2 and generator must be a power-th root of unity

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 ~generator ~power [y_0 ; y_1 ; ... y_n] computes the interpolation using FFT Cookey Tukey. The same conditions than for evaluation_fft must hold. x_0 must be the evaluation of the generator

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

polynomial_multiplication_fft ~generator:g ~power:n P Q computes the product P(X).Q(X) using FFT. g is a power-th roots of unity.

euclidian_division_opt P S returns the unique Q, R in AX such that P = Q * S + R if such exists, else None

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