package polynomial

  1. Overview
  2. Docs
package polynomial
Legend:
Library
Module
Module type
Parameter
Class
Class type

Make(Fp) builds a module of type T where the coefficients are in the prime field Fp

Parameters

module R : Ff_sig.PRIME

Signature

type scalar = R.t

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

type polynomial

Represents a polynomial

val zero : polynomial

Returns the polynomial P(X) = 0

val one : polynomial

Returns the polynomial P(X) = 1

Returns the degree of the polynomial

val degree_int : polynomial -> int

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

val have_same_degree : polynomial -> polynomial -> bool

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

val get_dense_polynomial_coefficients : polynomial -> scalar list

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}

val get_list_coefficients : polynomial -> (scalar * int) list

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 evaluation : polynomial -> scalar -> scalar

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

val constants : scalar -> polynomial

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)

val mult_by_scalar : scalar -> polynomial -> polynomial

mult_by_scalar s P returns s*P(X)

val is_null : polynomial -> bool

is_null P returns true iff P(X) = 0

val is_constant : polynomial -> bool

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

val opposite : polynomial -> polynomial

opposite P returns -P(X) where -P(X) = -a_nX^n - a_(n - 1) X^(n - 1) - ... - a_0

val equal : polynomial -> polynomial -> bool

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

val of_coefficients : ?remove_null_coefficients:bool -> (scalar * int) list -> polynomial

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.

val lagrange_interpolation : (scalar * scalar) list -> 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.

val even_polynomial : polynomial -> polynomial

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

val odd_polynomial : polynomial -> polynomial

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

val evaluation_fft : generator:scalar -> power:Z.t -> polynomial -> scalar list

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

val generate_random_polynomial : natural_with_infinity -> polynomial

generate_random_polynomial n returns a random polynomial of degree n

val get_highest_coefficient : polynomial -> scalar

get_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 -> polynomial

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

val polynomial_multiplication : polynomial -> polynomial -> polynomial

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

val polynomial_multiplication_fft : generator:scalar -> power:Z.t -> polynomial -> polynomial -> polynomial

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.

val euclidian_division_opt : polynomial -> polynomial -> (polynomial * polynomial) option

euclidian_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 * polynomial

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 (=) : polynomial -> polynomial -> bool

Infix operator for equal

Infix operator for add

Infix operator for polynomial_multiplication

Infix operator for sub