Struct Polynomial 

pub struct Polynomial<FE> {
    pub coefficients: Vec<FE>,
}

Represents the polynomial c_0 + c_1 * X + c_2 * X^2 + … + c_n * X^n as a vector of coefficients [c_0, c_1, ... , c_n]

Fields

coefficients: Vec<FE>

Implementations

impl<E: IsField> Polynomial<FieldElement<E>>

pub fn evaluate_fft<F: IsFFTField + IsSubFieldOf<E>>( poly: &Polynomial<FieldElement<E>>, blowup_factor: usize, domain_size: Option<usize>, ) -> Result<Vec<FieldElement<E>>, FFTError>

Returns N evaluations of this polynomial using FFT over a domain in a subfield F of E (so the results are P(w^i), with w being a primitive root of unity). N = max(self.coeff_len(), domain_size).next_power_of_two() * blowup_factor. If domain_size is None, it defaults to 0.

pub fn evaluate_offset_fft<F: IsFFTField + IsSubFieldOf<E>>( poly: &Polynomial<FieldElement<E>>, blowup_factor: usize, domain_size: Option<usize>, offset: &FieldElement<F>, ) -> Result<Vec<FieldElement<E>>, FFTError>

Returns N evaluations with an offset of this polynomial using FFT over a domain in a subfield F of E (so the results are P(w^i), with w being a primitive root of unity). N = max(self.coeff_len(), domain_size).next_power_of_two() * blowup_factor. If domain_size is None, it defaults to 0.

pub fn interpolate_fft<F: IsFFTField + IsSubFieldOf<E>>( fft_evals: &[FieldElement<E>], ) -> Result<Self, FFTError>

Returns a new polynomial that interpolates (w^i, fft_evals[i]), with w being a Nth primitive root of unity in a subfield F of E, and i in 0..N, with N = fft_evals.len(). This is considered to be the inverse operation of Self::evaluate_fft().

pub fn interpolate_offset_fft<F: IsFFTField + IsSubFieldOf<E>>( fft_evals: &[FieldElement<E>], offset: &FieldElement<F>, ) -> Result<Polynomial<FieldElement<E>>, FFTError>

Returns a new polynomial that interpolates offset (w^i, fft_evals[i]), with w being a Nth primitive root of unity in a subfield F of E, and i in 0..N, with N = fft_evals.len(). This is considered to be the inverse operation of Self::evaluate_offset_fft().

pub fn fast_fft_multiplication<F: IsFFTField + IsSubFieldOf<E>>( &self, other: &Self, ) -> Result<Self, FFTError>

Multiplies two polynomials using FFT. It’s faster than naive multiplication when the degree of the polynomials is large enough (>=26). This works best with polynomials whose highest degree is equal to a power of 2 - 1. Will return an error if the degree of the resulting polynomial is greater than 263.

This is an implementation of the fast division algorithm from Gathen’s book chapter 9

pub fn fast_division<F: IsSubFieldOf<E> + IsFFTField>( &self, divisor: &Self, ) -> Result<(Self, Self), FFTError>

Divides two polynomials with remainder. This is faster than the naive division if the degree of the divisor is greater than the degree of the dividend and both degrees are large enough.

pub fn invert_polynomial_mod<F: IsSubFieldOf<E> + IsFFTField>( &self, k: usize, ) -> Result<Self, FFTError>

Computes the inverse of polynomial P modulo x^k using Newton iteration. P must have an invertible constant term.

impl<F: IsField> Polynomial<FieldElement<F>>

pub fn new(coefficients: &[FieldElement<F>]) -> Self

Creates a new polynomial with the given coefficients

pub fn new_monomial(coefficient: FieldElement<F>, degree: usize) -> Self

Creates a new monomial term coefficient*x^degree

pub fn zero() -> Self

Creates the null polynomial

pub fn interpolate( xs: &[FieldElement<F>], ys: &[FieldElement<F>], ) -> Result<Self, InterpolateError>

Returns a polynomial that interpolates the points with x coordinates and y coordinates given by xs and ys. xs and ys must be the same length, and xs values should be unique. If not, panics. In short, it finds P(x) such that P(xs[i]) = ys[i]

pub fn evaluate<E>(&self, x: &FieldElement<E>) -> FieldElement<E>

where E: IsField, F: IsSubFieldOf<E>,

Evaluates a polynomial P(t) at a point x, using Horner’s algorithm Returns y = P(x)

pub fn evaluate_slice(&self, input: &[FieldElement<F>]) -> Vec<FieldElement<F>>

Evaluates a polynomial P(t) at a slice of points x Returns a vector y such that y[i] = P(input[i])

pub fn degree(&self) -> usize

Returns the degree of a polynomial, which corresponds to the highest power of x^d with non-zero coefficient

pub fn leading_coefficient(&self) -> FieldElement<F>

Returns the coefficient accompanying x^degree

pub fn coefficients(&self) -> &[FieldElement<F>]

Returns coefficients of the polynomial as an array [c_0, c_1, c_2, …, c_n] that represents the polynomial c_0 + c_1 * X + c_2 * X^2 + … + c_n * X^n

pub fn coeff_len(&self) -> usize

Returns the length of the vector of coefficients

pub fn differentiate(&self) -> Self

Returns the derivative of the polynomial with respect to x.

pub fn ruffini_division_inplace(&mut self, b: &FieldElement<F>)

Computes quotient with x - b in place.

pub fn ruffini_division<L>( &self, b: &FieldElement<L>, ) -> Polynomial<FieldElement<L>>

where L: IsField, F: IsSubFieldOf<L>,

Computes the quotient of the division of P(x) with x - b using Ruffini’s rule

pub fn long_division_with_remainder(self, dividend: &Self) -> (Self, Self)

Computes quotient and remainder of polynomial division.

Output: (quotient, remainder)

pub fn xgcd(&self, y: &Self) -> (Self, Self, Self)

Extended Euclidean Algorithm for polynomials.

This method computes the extended greatest common divisor (GCD) of two polynomials self and y. It returns a tuple of three elements: (a, b, g) such that a * self + b * y = g, where g is the greatest common divisor of self and y.

pub fn div_with_ref(self, dividend: &Self) -> Self

pub fn mul_with_ref(&self, factor: &Self) -> Self

pub fn scale<S: IsSubFieldOf<F>>(&self, factor: &FieldElement<S>) -> Self

Scales the coefficients of a polynomial P by a factor Returns P(factor * x)

pub fn scale_coeffs(&self, factor: &FieldElement<F>) -> Self

Multiplies all coefficients by a factor

pub fn break_in_parts(&self, number_of_parts: usize) -> Vec<Self>

Returns a vector of polynomials [p₀, p₁, …, p_{d-1}], where d is number_of_parts, such that self equals p₀(Xᵈ) + Xp₁(Xᵈ) + … + X^(d-1)p_{d-1}(Xᵈ).

Example: if d = 2 and self is 3 X^3 + X^2 + 2X + 1, then poly.break_in_parts(2) returns a vector with two polynomials (p₀, p₁), where p₀ = X + 1 and p₁ = 3X + 2.

pub fn to_extension<L: IsField>(self) -> Polynomial<FieldElement<L>>

where F: IsSubFieldOf<L>,

Embeds the coefficients of a polynomial into an extension field For example, given a polynomial with coefficients in F_p, returns the same polynomial with its coefficients as elements in F_{p^2}

pub fn truncate(&self, k: usize) -> Self

pub fn reverse(&self, d: usize) -> Self

impl<F: IsPrimeField> Polynomial<FieldElement<F>>

pub fn print_as_sage_poly(&self, var_name: Option<char>) -> String

Trait Implementations

impl<F, L> Add<&FieldElement<F>> for &Polynomial<FieldElement<L>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the + operator.

fn add(self, other: &FieldElement<F>) -> Polynomial<FieldElement<L>>

Performs the + operation.

impl<F, L> Add<&FieldElement<F>> for Polynomial<FieldElement<L>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the + operator.

fn add(self, other: &FieldElement<F>) -> Polynomial<FieldElement<L>>

Performs the + operation.

impl<F, L> Add<&Polynomial<FieldElement<L>>> for &FieldElement<F>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the + operator.

fn add(self, other: &Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>>

Performs the + operation.

impl<F, L> Add<&Polynomial<FieldElement<L>>> for &Polynomial<FieldElement<F>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the + operator.

fn add(self, a_polynomial: &Polynomial<FieldElement<L>>) -> Self::Output

Performs the + operation.

impl<F, L> Add<&Polynomial<FieldElement<L>>> for FieldElement<F>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the + operator.

fn add(self, other: &Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>>

Performs the + operation.

impl<F, L> Add<&Polynomial<FieldElement<L>>> for Polynomial<FieldElement<F>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the + operator.

fn add( self, a_polynomial: &Polynomial<FieldElement<L>>, ) -> Polynomial<FieldElement<L>>

Performs the + operation.

impl<F, L> Add<FieldElement<F>> for &Polynomial<FieldElement<L>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the + operator.

fn add(self, other: FieldElement<F>) -> Polynomial<FieldElement<L>>

Performs the + operation.

impl<F, L> Add<FieldElement<F>> for Polynomial<FieldElement<L>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the + operator.

fn add(self, other: FieldElement<F>) -> Polynomial<FieldElement<L>>

Performs the + operation.

impl<F, L> Add<Polynomial<FieldElement<L>>> for &FieldElement<F>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the + operator.

fn add(self, other: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>>

Performs the + operation.

impl<F, L> Add<Polynomial<FieldElement<L>>> for &Polynomial<FieldElement<F>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the + operator.

fn add( self, a_polynomial: Polynomial<FieldElement<L>>, ) -> Polynomial<FieldElement<L>>

Performs the + operation.

impl<F, L> Add<Polynomial<FieldElement<L>>> for FieldElement<F>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the + operator.

fn add(self, other: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>>

Performs the + operation.

impl<F, L> Add<Polynomial<FieldElement<L>>> for Polynomial<FieldElement<F>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the + operator.

fn add( self, a_polynomial: Polynomial<FieldElement<L>>, ) -> Polynomial<FieldElement<L>>

Performs the + operation.

impl<FE: Clone> Clone for Polynomial<FE>

fn clone(&self) -> Polynomial<FE>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<FE: Debug> Debug for Polynomial<FE>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<F> Div for Polynomial<FieldElement<F>>

where F: IsField,

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the / operator.

fn div( self, dividend: Polynomial<FieldElement<F>>, ) -> Polynomial<FieldElement<F>>

Performs the / operation.

impl<F, L> Mul<&FieldElement<F>> for &Polynomial<FieldElement<L>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the * operator.

fn mul(self, multiplicand: &FieldElement<F>) -> Polynomial<FieldElement<L>>

Performs the * operation.

impl<F, L> Mul<&FieldElement<F>> for Polynomial<FieldElement<L>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the * operator.

fn mul(self, multiplicand: &FieldElement<F>) -> Polynomial<FieldElement<L>>

Performs the * operation.

impl<F: IsField> Mul<&Polynomial<FieldElement<F>>> for &Polynomial<FieldElement<F>>

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the * operator.

fn mul( self, factor: &Polynomial<FieldElement<F>>, ) -> Polynomial<FieldElement<F>>

Performs the * operation.

impl<F: IsField> Mul<&Polynomial<FieldElement<F>>> for Polynomial<FieldElement<F>>

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the * operator.

fn mul( self, factor: &Polynomial<FieldElement<F>>, ) -> Polynomial<FieldElement<F>>

Performs the * operation.

impl<F, L> Mul<&Polynomial<FieldElement<L>>> for &FieldElement<F>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the * operator.

fn mul( self, multiplicand: &Polynomial<FieldElement<L>>, ) -> Polynomial<FieldElement<L>>

Performs the * operation.

impl<F, L> Mul<&Polynomial<FieldElement<L>>> for FieldElement<F>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the * operator.

fn mul( self, multiplicand: &Polynomial<FieldElement<L>>, ) -> Polynomial<FieldElement<L>>

Performs the * operation.

impl<F, L> Mul<FieldElement<F>> for &Polynomial<FieldElement<L>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the * operator.

fn mul(self, multiplicand: FieldElement<F>) -> Polynomial<FieldElement<L>>

Performs the * operation.

impl<F, L> Mul<FieldElement<F>> for Polynomial<FieldElement<L>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the * operator.

fn mul(self, multiplicand: FieldElement<F>) -> Polynomial<FieldElement<L>>

Performs the * operation.

impl<F: IsField> Mul<Polynomial<FieldElement<F>>> for &Polynomial<FieldElement<F>>

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the * operator.

fn mul(self, factor: Polynomial<FieldElement<F>>) -> Polynomial<FieldElement<F>>

Performs the * operation.

impl<F, L> Mul<Polynomial<FieldElement<L>>> for &FieldElement<F>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the * operator.

fn mul( self, multiplicand: Polynomial<FieldElement<L>>, ) -> Polynomial<FieldElement<L>>

Performs the * operation.

impl<F, L> Mul<Polynomial<FieldElement<L>>> for FieldElement<F>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the * operator.

fn mul( self, multiplicand: Polynomial<FieldElement<L>>, ) -> Polynomial<FieldElement<L>>

Performs the * operation.

impl<F: IsField> Mul for Polynomial<FieldElement<F>>

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the * operator.

fn mul(self, factor: Polynomial<FieldElement<F>>) -> Polynomial<FieldElement<F>>

Performs the * operation.

impl<F: IsField> Neg for &Polynomial<FieldElement<F>>

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

fn neg(self) -> Polynomial<FieldElement<F>>

Performs the unary - operation.

impl<F: IsField> Neg for Polynomial<FieldElement<F>>

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

fn neg(self) -> Polynomial<FieldElement<F>>

Performs the unary - operation.

impl<FE: PartialEq> PartialEq for Polynomial<FE>

fn eq(&self, other: &Polynomial<FE>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<F, L> Sub<&FieldElement<F>> for &Polynomial<FieldElement<L>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the - operator.

fn sub(self, other: &FieldElement<F>) -> Polynomial<FieldElement<L>>

Performs the - operation.

impl<F, L> Sub<&FieldElement<F>> for Polynomial<FieldElement<L>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the - operator.

fn sub(self, other: &FieldElement<F>) -> Polynomial<FieldElement<L>>

Performs the - operation.

impl<F, L> Sub<&Polynomial<FieldElement<L>>> for &FieldElement<F>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the - operator.

fn sub(self, other: &Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>>

Performs the - operation.

impl<F, L> Sub<&Polynomial<FieldElement<L>>> for &Polynomial<FieldElement<F>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the - operator.

fn sub( self, substrahend: &Polynomial<FieldElement<L>>, ) -> Polynomial<FieldElement<L>>

Performs the - operation.

impl<F, L> Sub<&Polynomial<FieldElement<L>>> for FieldElement<F>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the - operator.

fn sub(self, other: &Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>>

Performs the - operation.

impl<F, L> Sub<&Polynomial<FieldElement<L>>> for Polynomial<FieldElement<F>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the - operator.

fn sub( self, substrahend: &Polynomial<FieldElement<L>>, ) -> Polynomial<FieldElement<L>>

Performs the - operation.

impl<F, L> Sub<FieldElement<F>> for &Polynomial<FieldElement<L>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the - operator.

fn sub(self, other: FieldElement<F>) -> Polynomial<FieldElement<L>>

Performs the - operation.

impl<F, L> Sub<FieldElement<F>> for Polynomial<FieldElement<L>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the - operator.

fn sub(self, other: FieldElement<F>) -> Polynomial<FieldElement<L>>

Performs the - operation.

impl<F, L> Sub<Polynomial<FieldElement<L>>> for &FieldElement<F>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the - operator.

fn sub(self, other: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>>

Performs the - operation.

impl<F, L> Sub<Polynomial<FieldElement<L>>> for &Polynomial<FieldElement<F>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the - operator.

fn sub( self, substrahend: Polynomial<FieldElement<L>>, ) -> Polynomial<FieldElement<L>>

Performs the - operation.

impl<F, L> Sub<Polynomial<FieldElement<L>>> for FieldElement<F>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the - operator.

fn sub(self, other: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>>

Performs the - operation.

impl<F, L> Sub<Polynomial<FieldElement<L>>> for Polynomial<FieldElement<F>>

where L: IsField, F: IsSubFieldOf<L>,

type Output = Polynomial<FieldElement<L>>

The resulting type after applying the - operator.

fn sub( self, substrahend: Polynomial<FieldElement<L>>, ) -> Polynomial<FieldElement<L>>

Performs the - operation.

impl<FE: Eq> Eq for Polynomial<FE>

impl<FE> StructuralPartialEq for Polynomial<FE>