The type of the polynomial coefficients. Can be a field or more generally a ring. For the moment, it is restricted to prime fields.
val zero : tReturns the polynomial P(X) = 0
val one : tReturns the polynomial P(X) = 1
val degree : t -> natural_with_infinityReturns the degree of the polynomial
val degree_int : t -> inthave_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_
a_
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_
a_
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
val is_null : t -> boolis_null P returns true iff P(X) = 0
val is_constant : t -> boolis_constant P returns true iff P(X) = s for s scalar
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}).
val generate_random_polynomial : natural_with_infinity -> tgenerate_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
val to_string : t -> string