Struct twenty_first::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<S, XF>(&self, alpha: S) -> Polynomial<XF>

where S: Clone + One, FF: Mul<S, Output = XF>, XF: FiniteField,

Return the polynomial which corresponds to the transformation x → α·x.

Given a polynomial P(x), produce P’(x) := P(α·x). Evaluating P’(x) then corresponds to evaluating P(α·x).

pub fn fast_square(&self) -> Self

It is the caller’s responsibility that this function is called with sufficiently large input to be safe and to be faster than square.

pub fn square(&self) -> Self

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

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

Multiply self by other.

Prefer this over self * other since it chooses the fastest multiplication strategy.

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

Compute the lowest degree polynomial with the provided roots.

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

Construct the lowest-degree polynomial interpolating the given points.

let domain = bfe_vec![0, 1, 2, 3];
let values = bfe_vec![1, 3, 5, 7];
let polynomial = Polynomial::interpolate(&domain, &values);

assert_eq!(1, polynomial.degree());
assert_eq!(bfe!(9), polynomial.evaluate(bfe!(4)));

Panics

• Panics if the provided domain is empty.
• Panics if the provided domain and values are not of the same length.

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

pub fn batch_evaluate(&self, domain: &[FF]) -> Vec<FF>

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

where S: Clone + One, FF: Mul<S, Output = FF>,

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

Performance

If possible, use a base field element as the offset.

Panics

Panics if the order of the domain generated by the generator is smaller than or equal to the degree of self.

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

where S: Clone + One + Inverse, FF: Mul<S, Output = FF>,

The inverse of Self::fast_coset_evaluate.

Performance

If possible, use a base field element as the offset.

Panics

Panics if the length of values does not equal the order of the domain generated by the generator.

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

Divide self by some divisor.

Panics

Panics if the divisor is zero.

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

The degree-k polynomial with the same k + 1 leading coefficients as self. To be more precise: The degree of the result will be the minimum of k and Self::degree(). This implies, among other things, that if self is zero, the result will also be zero, independent of k.

Examples

let f = Polynomial::new(bfe_vec![0, 1, 2, 3, 4]); // 4x⁴ + 3x³ + 2x² + 1x¹ + 0
let g = f.truncate(2);                            // 4x² + 3x¹ + 2
assert_eq!(Polynomial::new(bfe_vec![2, 3, 4]), g);

pub fn mod_x_to_the_n(&self, n: usize) -> Self

self % x^n

A special case of Self::rem, and faster.

Examples

let f = Polynomial::new(bfe_vec![0, 1, 2, 3, 4]); // 4x⁴ + 3x³ + 2x² + 1x¹ + 0
let g = f.mod_x_to_the_n(2);                      // 1x¹ + 0
assert_eq!(Polynomial::new(bfe_vec![0, 1]), g);

impl Polynomial<BFieldElement>

pub fn clean_divide(self, divisor: Self) -> Self

A fast way of dividing two polynomials. Only works if division is clean, i.e., if the remainder of polynomial long division is zero. This must be known ahead of time. If division is unclean, this method might panic or produce a wrong result. Use Polynomial::divide for more generality.

Panics

Panics if

• the divisor is zero, or
• division is not clean, i.e., if polynomial long division leaves some non-zero remainder.

impl<FF: FiniteField> Polynomial<FF>

pub const fn new(coefficients: Vec<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>

The coefficient of the polynomial’s term of highest power. None if (and only if) self is zero.

Furthermore, is never Some(FF::zero()).

Examples

let f = Polynomial::new(bfe_vec![1, 2, 3]);
assert_eq!(Some(bfe!(3)), f.leading_coefficient());
assert_eq!(None, Polynomial::<XFieldElement>::zero().leading_coefficient());

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 slow_square(&self) -> Self

Slow square implementation that does not use NTT

impl<FF: FiniteField> Polynomial<FF>

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

impl<FF: FiniteField> Polynomial<FF>

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

Multiply a polynomial with itself pow times

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

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

Multiply a polynomial with x^power

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

Multiply a polynomial with a scalar, i.e., compute scalar · self(x).

Slightly faster than Self::scalar_mul.

Examples

let mut f = Polynomial::new(bfe_vec![1, 2, 3]);
f.scalar_mul_mut(bfe!(2));
assert_eq!(Polynomial::new(bfe_vec![2, 4, 6]), f);

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

Multiply a polynomial with a scalar, i.e., compute scalar · self(x).

Slightly slower than Self::scalar_mul_mut.

Examples

let f = Polynomial::new(bfe_vec![1, 2, 3]);
let g = f.scalar_mul(bfe!(2));
assert_eq!(Polynomial::new(bfe_vec![2, 4, 6]), g);

impl<FF: FiniteField> Polynomial<FF>

pub fn xgcd(x: Self, y: Self) -> (Self, Self, Self)

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

Example

let x = Polynomial::<BFieldElement>::from([1, 0, 1]);
let y = Polynomial::<BFieldElement>::from([1, 1]);
let (gcd, a, b) = Polynomial::xgcd(x.clone(), y.clone());
assert_eq!(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 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 for Polynomial<FF>

fn add_assign(&mut self, rhs: Self)

Performs the += operation.

impl<'arbitrary, FF: FiniteField + Arbitrary<'arbitrary>> Arbitrary<'arbitrary> for Polynomial<FF>

fn arbitrary(u: &mut Unstructured<'arbitrary>) -> Result<Self>

Generate an arbitrary value of Self from the given unstructured data.

fn arbitrary_take_rest(u: Unstructured<'arbitrary>) -> Result<Self>

Generate an arbitrary value of Self from the entirety of the given unstructured data.

fn size_hint(depth: usize) -> (usize, Option<usize>)

Get a size hint for how many bytes out of an Unstructured this type needs to construct itself.

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 for Polynomial<FF>

type Output = Polynomial<FF>

The resulting type after applying the / operator.

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

Performs the / operation.

impl<FF, E> From<&[E]> for Polynomial<FF>

where FF: FiniteField, E: Into<FF> + Clone,

fn from(coefficients: &[E]) -> Self

Converts to this type from the input type.

impl<FF, E> From<&Vec<E>> for Polynomial<FF>

where FF: FiniteField, E: Into<FF> + Clone,

fn from(coefficients: &Vec<E>) -> Self

Converts to this type from the input type.

impl<const N: usize, FF, E> From<[E; N]> for Polynomial<FF>

where FF: FiniteField, E: Into<FF>,

fn from(coefficients: [E; N]) -> Self

Converts to this type from the input type.

impl From<Polynomial<BFieldElement>> for XFieldElement

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

Converts to this type from the input type.

impl<FF, E> From<Vec<E>> for Polynomial<FF>

where FF: FiniteField, E: Into<FF>,

fn from(coefficients: Vec<E>) -> 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 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> Neg for Polynomial<FF>

type Output = Polynomial<FF>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - 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 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 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 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>