Struct twenty_first::shared_math::polynomial::Polynomial

pub struct Polynomial<FF: FiniteField> {
    pub coefficients: Vec<FF>,
}

Fields

coefficients: Vec<FF>

Implementations

impl<FF> Polynomial<FF>where
    FF: FiniteField + MulAssign<BFieldElement>,

pub fn scale(&self, alpha: &BFieldElement) -> Self

pub fn fast_square(&self) -> Self

pub fn square(&self) -> Self

pub fn fast_mod_pow(&self, pow: BigInt) -> Self

pub fn fast_multiply(
    lhs: &Self,
    rhs: &Self,
    primitive_root: &BFieldElement,
    root_order: usize
) -> Self

pub fn fast_zerofier(
    domain: &[FF],
    primitive_root: &BFieldElement,
    root_order: usize
) -> Self

pub fn fast_evaluate(
    &self,
    domain: &[FF],
    primitive_root: &BFieldElement,
    root_order: usize
) -> Vec<FF>

pub fn fast_interpolate(
    domain: &[FF],
    values: &[FF],
    primitive_root: &BFieldElement,
    root_order: usize
) -> Self

pub fn batch_fast_interpolate(
    domain: &[FF],
    values_matrix: &Vec<Vec<FF>>,
    primitive_root: &BFieldElement,
    root_order: usize
) -> Vec<Self>

pub fn fast_coset_evaluate(
    &self,
    offset: &BFieldElement,
    generator: BFieldElement,
    order: usize
) -> Vec<FF>

Fast evaluate on a coset domain, which is the group generated by generator^i * offset

pub fn fast_coset_interpolate(
    offset: &BFieldElement,
    generator: BFieldElement,
    values: &[FF]
) -> Self

The inverse of fast_coset_evaluate

pub fn fast_coset_divide(
    lhs: &Polynomial<FF>,
    rhs: &Polynomial<FF>,
    offset: BFieldElement,
    primitive_root: BFieldElement,
    root_order: usize
) -> Polynomial<FF>

Divide two polynomials under the homomorphism of evaluation for a N^2 -> N*log(N) speedup Since we often want to use this fast division for numerators and divisors that evaluate to zero in their domain, we do the division with an offset from the polynomials’ original domains. The issue of zero in the numerator and divisor arises when we divide a transition polynomial with a zerofier.

impl<FF: FiniteField> Polynomial<FF>

pub const fn new(coefficients: Vec<FF>) -> Self

pub fn new_const(element: FF) -> Self

pub fn normalize(&mut self)

pub fn from_constant(constant: FF) -> Self

pub fn is_x(&self) -> bool

pub fn evaluate(&self, x: &FF) -> FF

pub fn leading_coefficient(&self) -> Option<FF>

pub fn lagrange_interpolate(domain: &[FF], values: &[FF]) -> Self

pub fn are_colinear_3(p0: (FF, FF), p1: (FF, FF), p2: (FF, FF)) -> bool

pub fn get_colinear_y(p0: (FF, FF), p1: (FF, FF), p2_x: FF) -> FF

pub fn zerofier(domain: &[FF]) -> Self

pub fn slow_square(&self) -> Self

impl<FF: FiniteField> Polynomial<FF>

pub fn are_colinear(points: &[(FF, FF)]) -> bool

pub fn lagrange_interpolate_zipped(points: &[(FF, FF)]) -> Self

impl<FF: FiniteField> Polynomial<FF>

pub fn multiply(self, other: Self) -> Self

pub fn mod_pow(&self, pow: BigInt) -> Self

pub fn shift_coefficients_mut(&mut self, power: usize, zero: FF)

pub fn shift_coefficients(&self, power: usize) -> Self

pub fn scalar_mul_mut(&mut self, scalar: FF)

pub fn scalar_mul(&self, scalar: FF) -> Self

pub fn divide(&self, divisor: Self) -> (Self, Self)

Return (quotient, remainder)

impl<FF: FiniteField> Polynomial<FF>

pub fn xgcd(
    x: Polynomial<FF>,
    y: Polynomial<FF>
) -> (Polynomial<FF>, Polynomial<FF>, Polynomial<FF>)

Extended Euclidean algorithm with polynomials. Computes the greatest common divisor gcd as a monic polynomial, as well as the corresponding Bézout coefficients a and b, satisfying gcd = a·x + b·y

impl<FF: FiniteField> Polynomial<FF>

pub fn degree(&self) -> isize

pub fn formal_derivative(&self) -> Self

Trait Implementations

impl<FF: FiniteField> Add<Polynomial<FF>> for Polynomial<FF>

type Output = Polynomial<FF>

The resulting type after applying the + operator.

fn add(self, other: Self) -> Self

Performs the + operation.

impl<FF: FiniteField> AddAssign<Polynomial<FF>> for Polynomial<FF>

fn add_assign(&mut self, rhs: Self)

Performs the += operation.

impl<FF: Clone + FiniteField> Clone for Polynomial<FF>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<FF: FiniteField> Debug for Polynomial<FF>

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

Formats the value using the given formatter.

impl<FF: FiniteField> Display for Polynomial<FF>

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

Formats the value using the given formatter.

impl<FF: FiniteField> Div<Polynomial<FF>> for Polynomial<FF>

type Output = Polynomial<FF>

The resulting type after applying the / operator.

fn div(self, other: Self) -> Self

Performs the / operation.

impl From<Polynomial<BFieldElement>> for XFieldElement

fn from(poly: Polynomial<BFieldElement>) -> Self

Converts to this type from the input type.

impl From<XFieldElement> for Polynomial<BFieldElement>

fn from(item: XFieldElement) -> Self

Converts to this type from the input type.

impl<FF: FiniteField> Hash for Polynomial<FF>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)where
    H: Hasher,
    Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<FF: FiniteField> Mul<Polynomial<FF>> for Polynomial<FF>

type Output = Polynomial<FF>

The resulting type after applying the * operator.

fn mul(self, other: Self) -> Self

Performs the * operation.

impl<FF: FiniteField> One for Polynomial<FF>

fn one() -> Self

Returns the multiplicative identity element of Self, 1.

fn is_one(&self) -> bool

Returns true if self is equal to the multiplicative identity.

fn set_one(&mut self)

Sets self to the multiplicative identity element of Self, 1.

impl<FF: FiniteField> PartialEq<Polynomial<FF>> for Polynomial<FF>

fn eq(&self, other: &Self) -> 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<FF: FiniteField> Rem<Polynomial<FF>> for Polynomial<FF>

type Output = Polynomial<FF>

The resulting type after applying the % operator.

fn rem(self, other: Self) -> Self

Performs the % operation.

impl<FF: FiniteField> Sub<Polynomial<FF>> for Polynomial<FF>

type Output = Polynomial<FF>

The resulting type after applying the - operator.

fn sub(self, other: Self) -> Self

Performs the - operation.

impl<FF: FiniteField> Zero for Polynomial<FF>

fn zero() -> Self

Returns the additive identity element of Self, 0.

fn is_zero(&self) -> bool

Returns true if self is equal to the additive identity.

fn set_zero(&mut self)

Sets self to the additive identity element of Self, 0.

impl<FF: FiniteField> Eq for Polynomial<FF>