On This Page
Legend:
Library
Module
Module type
Parameter
Class
Class type
Library
Module
Module type
Parameter
Class
Class type
package polynomial
Make(Fp) builds a module of type T where the coefficients are in the prime field Fp
Parameters
module R : Ff_sig.PRIMESignature
type scalar = R.tThe 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 : polynomialReturns the polynomial P(X) = 0
val one : polynomialReturns the polynomial P(X) = 1
val degree : polynomial -> natural_with_infinityReturns the degree of the polynomial
val degree_int : polynomial -> intdegree_int P returns the degree of P as an integer. If P(X) = 0, returns -1
val have_same_degree : polynomial -> polynomial -> boolhave_same_degree P Q returns true if P and Q have the same degree
val get_dense_polynomial_coefficients : polynomial -> scalar listget_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_
a_
X + ... + a_
n - 1X^n - 1, the function will returna_{n - 1}, ..., a_{0}
val get_list_coefficients : polynomial -> (scalar * int) listget_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 -> scalarevaluation P s computes P(s). Use Horner's method in O(n).
val constants : scalar -> polynomialconstants s returns the constant polynomial P(X) = s
val add : polynomial -> polynomial -> polynomialadd P Q returns P(X) + Q(X)
val sub : polynomial -> polynomial -> polynomialsub P Q returns P(X) - Q(X)
val mult_by_scalar : scalar -> polynomial -> polynomialmult_by_scalar s P returns s*P(X)
val is_null : polynomial -> boolis_null P returns true iff P(X) = 0
val is_constant : polynomial -> boolis_constant P returns true iff P(X) = s for s scalar
val opposite : polynomial -> polynomialopposite P returns -P(X) where -P(X) = -a_nX^n - a_(n - 1) X^(n - 1) - ... - a_0
val equal : polynomial -> polynomial -> boolequal P Q returns true iff P(X) = Q(X) on S
val of_coefficients :
?remove_null_coefficients:bool ->
(scalar * int) list ->
polynomialof_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 -> polynomiallagrange_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 -> polynomialeven_polynomial P returns the polynomial P_even containing only the even coefficients of P
val odd_polynomial : polynomial -> polynomialodd_polynomial P returns the polynomial P_odd containing only the odd coefficients of P
val evaluation_fft : generator:scalar -> power:Z.t -> polynomial -> scalar listevaluate_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
val generate_random_polynomial : natural_with_infinity -> polynomialgenerate_random_polynomial n returns a random polynomial of degree n
val get_highest_coefficient : polynomial -> scalarget_highest_coefficient P where P(X) = a_n X^n + ... a_0 returns a_n
val interpolation_fft :
generator:scalar ->
power:Z.t ->
scalar list ->
polynomialinterpolation_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
val polynomial_multiplication : polynomial -> polynomial -> polynomialpolynomial_multiplication P Q computes the product P(X).Q(X)
val polynomial_multiplication_fft :
generator:scalar ->
power:Z.t ->
polynomial ->
polynomial ->
polynomialpolynomial_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.
val euclidian_division_opt :
polynomial ->
polynomial ->
(polynomial * polynomial) optioneuclidian_division_opt P S returns the unique Q, R in AX such that P = Q * S + R if such exists, else None
val extended_euclide :
polynomial ->
polynomial ->
polynomial * polynomial * polynomialextended_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 -> boolInfix operator for equal
val (+) : polynomial -> polynomial -> polynomialInfix operator for add
val (*) : polynomial -> polynomial -> polynomialInfix operator for polynomial_multiplication
val (-) : polynomial -> polynomial -> polynomialInfix operator for sub
On This Page