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

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

get_dense_polynomial_coefficients P returns the list of the coefficients of P, including the null coefficients, in decreasing order i.e. if P(X) = a_{0} + a_{1} X + ... + a_{n - 1} X^{n - 1}, the function will return a_{n - 1}, ..., a_{0}

get_dense_polynomial_coefficients_with_degree P returns the list of the coefficients of P with the degree as a tuple, including the null coefficients, in decreasing order i.e. if P(X) = a_{0} + a_{1} X + ... + a_{n - 1} X^{n - 1}, the function will return (a_{n - 1}, n -1), ..., (a_{0}, 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 t.

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

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_imperative ~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. Larger polynomials can also be used but the implementation is not the most memory efficient yet and must be improved. The complexity is in O(n log(m)) where n is the domain size and m the degree of the polynomial. When m is smaller than n, the polynomial is padded with zeroes to reach n coefficients. 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