polynomial 0.4.0 (latest) · OCaml Package

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 t

Represents a polynomial

val zero : t

Returns the polynomial P(X) = 0

val one : t

Returns the polynomial P(X) = 1

val degree : t -> natural_with_infinity

Returns the degree of the polynomial

val degree_int : t -> int

val have_same_degree : t -> t -> bool

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

val get_dense_polynomial_coefficients : t -> scalar list

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}

val get_dense_polynomial_coefficients_with_degree : t -> (scalar * int) list

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

val get_list_coefficients : t -> (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 : t -> scalar -> scalar

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

val constants : scalar -> t

constants s returns the constant polynomial P(X) = s

val add : t -> t -> t

add P Q returns P(X) + Q(X)

val sub : t -> t -> t

sub P Q returns P(X) - Q(X)

val mult_by_scalar : scalar -> t -> t

mult_by_scalar s P returns s*P(X)

val is_null : t -> bool

is_null P returns true iff P(X) = 0

val is_constant : t -> bool

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

val opposite : t -> t

opposite P returns -P(X)

val equal : t -> t -> bool

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

val of_coefficients : (scalar * int) list -> t

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.

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

val even_polynomial : t -> t

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

val odd_polynomial : t -> t

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

val evaluation_fft : domain:scalar array -> t -> scalar list

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

generate_random_polynomial n returns a random polynomial of degree n

val get_highest_coefficient : t -> scalar

get_highest_coefficient P where P(X) = a_n X^n + ... a_0 returns a_n

val interpolation_fft : domain:scalar array -> scalar list -> t

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.

val polynomial_multiplication : t -> t -> t

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

val polynomial_multiplication_fft : domain:scalar array -> t -> t -> t

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

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

val extended_euclide : t -> t -> t * t * t

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

Infix operator for equal

val (+) : t -> t -> t

Infix operator for add

val (*) : t -> t -> t

Infix operator for polynomial_multiplication

val (-) : t -> t -> t

Infix operator for sub

val to_string : t -> string

package polynomial

Parameters

Signature