Struct lambdaworks_math::polynomial::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<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

pub fn zero() -> Self

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.

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

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

pub fn degree(&self) -> usize

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

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

pub fn pad_with_zero_coefficients_to_length(pa: &mut Self, n: usize)

pub fn pad_with_zero_coefficients(pa: &Self, pb: &Self) -> (Self, Self)

Pads polynomial representations with minimum number of zeros to match lengths.

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

Computes quotient with x - b in place.

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

Computes quotient and remainder of polynomial division.

Output: (quotient, remainder)

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

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

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

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

pub fn even_odd_decomposition(&self) -> (Self, Self)

For the given polynomial, returns a tuple (even, odd) of polynomials with the even and odd coefficients respectively. Note that even and odd ARE NOT actually even/odd polynomials themselves.

Example: if poly = 3 X^3 + X^2 + 2X + 1, then poly.even_odd_decomposition = (even, odd) with even = X + 1 and odd = 3X + 1.

In general, the decomposition satisfies the following: poly(x) = even(x^2) + X * odd(x^2)

Trait Implementations

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the + operator.

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

Performs the + operation.

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

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

Returns a copy 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: IsField> Div<Polynomial<FieldElement<F>>> for Polynomial<FieldElement<F>>

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: IsFFTField> FFTPoly<F> for Polynomial<FieldElement<F>>

fn evaluate_fft( &self, blowup_factor: usize, domain_size: Option<usize> ) -> Result<Vec<FieldElement<F>>, FFTError>

Returns N evaluations of this polynomial using FFT (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.

fn evaluate_offset_fft( &self, blowup_factor: usize, domain_size: Option<usize>, offset: &FieldElement<F> ) -> Result<Vec<FieldElement<F>>, FFTError>

Returns N evaluations with an offset of this polynomial using FFT (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.

fn interpolate_fft(fft_evals: &[FieldElement<F>]) -> Result<Self, FFTError>

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

fn interpolate_offset_fft( fft_evals: &[FieldElement<F>], offset: &FieldElement<F> ) -> Result<Polynomial<FieldElement<F>>, FFTError>

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

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the * operator.

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

Performs the * operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the * operator.

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

Performs the * operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the * operator.

fn mul( self, multiplicand: &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: IsField> Mul<&Polynomial<FieldElement<F>>> for FieldElement<F>

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the * operator.

fn mul( self, multiplicand: &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: IsField> Mul<FieldElement<F>> for &Polynomial<FieldElement<F>>

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the * operator.

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

Performs the * operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the * operator.

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

Performs the * operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the * operator.

fn mul( self, multiplicand: 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: IsField> Mul<Polynomial<FieldElement<F>>> for FieldElement<F>

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the * operator.

fn mul( self, multiplicand: 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: 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<Polynomial<FE>> for Polynomial<FE>

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

This method tests for self and other values to be equal, and is used by ==.

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

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

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Polynomial<FieldElement<F>>

The resulting type after applying the - operator.

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

Performs the - operation.

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

impl<FE> StructuralEq for Polynomial<FE>

impl<FE> StructuralPartialEq for Polynomial<FE>