Struct Polynomial

pub struct Polynomial<'coeffs, FF: FiniteField> { /* private fields */ }

A univariate polynomial with coefficients in a finite field, in monomial form.

Implementations

impl<FF> Polynomial<'_, FF>

where FF: FiniteField,

pub fn degree(&self) -> isize

pub fn coefficients(&self) -> &[FF]

The polynomial’s coefficients, in order of increasing degree. That is, the leading coefficient is the slice’s last element.

The leading coefficient is guaranteed to be non-zero. Consequently, the zero-polynomial is the empty slice.

See also into_coefficients().

pub fn into_coefficients(self) -> Vec<FF>

Like coefficients(), but consumes self.

Only clones the underlying coefficients if they are not already owned.

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 is_x(&self) -> bool

pub fn formal_derivative(&self) -> Polynomial<'static, FF>

pub fn evaluate<Ind, Eval>(&self, x: Ind) -> Eval

where Ind: Clone, Eval: Mul<Ind, Output = Eval> + Add<FF, Output = Eval> + Zero,

Evaluate self in an indeterminate.

For a specialized version, with fewer type annotations needed, see Self::evaluate_in_same_field.

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

Evaluate self in an indeterminate.

For a generalized version, with more type annotations needed, see Self::evaluate.

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

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

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

pub fn slow_square(&self) -> Polynomial<'static, FF>

Slow square implementation that does not use NTT

pub fn pow(&self, pow: u32) -> Polynomial<'static, FF>

Multiply self with itself pow times.

Similar to Self::fast_pow, but slower and slightly more general.

pub fn mod_pow(&self, pow: BigInt) -> Polynomial<'static, FF>

👎Deprecated since 0.42.0: renaming; use pow instead

pub fn shift_coefficients(self, power: usize) -> Polynomial<'static, FF>

Multiply a polynomial with x^power

pub fn scalar_mul_mut<S>(&mut self, scalar: S)

where S: Clone, FF: MulAssign<S>,

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

Slightly faster but slightly less general 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<S, FF2>(&self, scalar: S) -> Polynomial<'static, FF2>

where S: Clone, FF: Mul<S, Output = FF2>, FF2: FiniteField,

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

Slightly slower but slightly more general 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);

pub fn divide( &self, divisor: &Polynomial<'_, FF>, ) -> (Polynomial<'static, FF>, Polynomial<'static, FF>)

Divide self by some divisor, returning (quotient, remainder).

Panics

Panics if the divisor is zero.

pub fn xgcd( x: Self, y: Polynomial<'_, FF>, ) -> (Polynomial<'static, FF>, Polynomial<'static, FF>, Polynomial<'static, 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

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

pub fn into_owned(self) -> Polynomial<'static, FF>

Return a polynomial that owns its coefficients. Clones the coefficients if they are not already owned.

impl<FF> Polynomial<'_, FF>

where FF: FiniteField + MulAssign<BFieldElement>,

pub fn scale<S, XF>(&self, alpha: S) -> Polynomial<'static, 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) -> Polynomial<'static, FF>

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) -> Polynomial<'static, FF>

pub fn fast_pow(&self, pow: u32) -> Polynomial<'static, FF>

Multiply self with itself pow times.

Similar to Self::pow, but faster and slightly less general.

pub fn fast_mod_pow(&self, pow: BigInt) -> Polynomial<'static, FF>

👎Deprecated since 0.42.0: renaming; use fast_pow instead

pub fn multiply<FF2>( &self, other: &Polynomial<'_, FF2>, ) -> Polynomial<'static, <FF as Mul<FF2>>::Output>

where FF: Mul<FF2>, FF2: FiniteField + MulAssign<BFieldElement>, <FF as Mul<FF2>>::Output: FiniteField + MulAssign<BFieldElement>,

Multiply self by other.

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

pub fn batch_multiply(factors: &[Self]) -> Polynomial<'static, FF>

Multiply a bunch of polynomials together.

pub fn par_batch_multiply(factors: &[Self]) -> Polynomial<'static, FF>

Parallel version of batch_multiply.

pub fn reduce(&self, modulus: &Polynomial<'_, FF>) -> Polynomial<'static, FF>

Divide (with remainder) and throw away the quotient. Note that the self object is the numerator and the argument is the denominator (or modulus).

pub fn fast_reduce(&self, modulus: &Self) -> Polynomial<'static, FF>

Compute the remainder after division of one polynomial by another. This method first reduces the numerator by a multiple of the denominator that was constructed to enable NTT-based chunk-wise reduction, before invoking the standard long division based algorithm to finalize. As a result, it works best for large numerators being reduced by small denominators.

pub fn structured_multiple_of_degree(&self, n: usize) -> Polynomial<'static, FF>

Given a polynomial f(X) and an integer n, find a multiple of f(X) of the form X^n + (something of much smaller degree).

Panics

Panics if the polynomial is zero, or if its degree is larger than n

pub fn formal_power_series_inverse_newton( self, precision: usize, ) -> Polynomial<'static, FF>

Compute a polynomial g(X) from a given polynomial f(X) such that g(X) * f(X) = 1 mod X^n , where n is the precision.

In formal terms, g(X) is the approximate multiplicative inverse in the formal power series ring, where elements obey the same algebraic rules as polynomials do but can have an infinite number of coefficients. To represent these elements on a computer, one has to truncate the coefficient vectors somewhere. The resulting truncation error is considered “small” when it lives on large powers of X. This function works by applying Newton’s method in this ring.

Example

let precision = 8;
let f = Polynomial::new(bfe_vec![42; precision]);
let g = f.clone().formal_power_series_inverse_newton(precision);
let x_to_the_n = Polynomial::one().shift_coefficients(precision);
let (_quotient, remainder) = g.multiply(&f).divide(&x_to_the_n);
assert!(remainder.is_one());

Panics

Panics when f(X) is not invertible in the formal power series ring, i.e., when its constant coefficient is zero.

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

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

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.

impl<FF> Polynomial<'static, FF>

where FF: FiniteField + MulAssign<BFieldElement>,

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

Compute the lowest degree polynomial with the provided roots. Also known as “vanishing polynomial.”

Example

let roots = bfe_array![2, 4, 6];
let zerofier = Polynomial::zerofier(&roots);

assert_eq!(3, zerofier.degree());
assert_eq!(bfe_vec![0, 0, 0], zerofier.batch_evaluate(&roots));

let  non_roots = bfe_vec![0, 1, 3, 5];
assert!(zerofier.batch_evaluate(&non_roots).iter().all(|x| !x.is_zero()));

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

Parallel version of zerofier.

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 par_interpolate(domain: &[FF], values: &[FF]) -> Self

Parallel version of interpolate.

Panics

See interpolate.

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

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

Evaluate the polynomial on a batch of points.

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

Parallel version of batch_evaluate.

pub fn fast_coset_interpolate<S>(offset: S, 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 is

• not a power of 2
• larger than u32::MAX

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

pub fn coset_extrapolate( domain_offset: BFieldElement, codeword: &[FF], points: &[FF], ) -> Vec<FF>

Extrapolate a Reed-Solomon codeword, defined relative to a coset of the subgroup of order n (codeword length), in new points.

pub fn batch_coset_extrapolate( domain_offset: BFieldElement, codeword_length: usize, codewords: &[FF], points: &[FF], ) -> Vec<FF>

Extrapolate many Reed-Solomon codewords, defined relative to the same coset of the subgroup of order codeword_length, in the same set of new points.

Example

let n = 1 << 5;
let domain_offset = bfe!(7);
let codewords = [bfe_vec![3; n], bfe_vec![2; n]].concat();
let points = bfe_vec![0, 1];
assert_eq!(
    bfe_vec![3, 3, 2, 2],
    Polynomial::<BFieldElement>::batch_coset_extrapolate(
        domain_offset,
        n,
        &codewords,
        &points
    )
);

Panics

Panics if the codeword_length is not a power of two.

pub fn par_batch_coset_extrapolate( domain_offset: BFieldElement, codeword_length: usize, codewords: &[FF], points: &[FF], ) -> Vec<FF>

Parallel version of batch_coset_extrapolate.

impl Polynomial<'_, BFieldElement>

pub fn clean_divide(self, divisor: Self) -> Polynomial<'static, BFieldElement>

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> Polynomial<'static, FF>

where FF: FiniteField,

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

Create a new polynomial with the given coefficients. The first coefficient is the constant term, the last coefficient has the highest degree.

See also Self::new_borrowed.

pub fn x_to_the(n: usize) -> Self

x^n

pub fn from_constant(constant: FF) -> Self

impl<'coeffs, FF> Polynomial<'coeffs, FF>

where FF: FiniteField,

pub fn new_borrowed(coefficients: &'coeffs [FF]) -> Self

Like Self::new, but without owning the coefficients.

Trait Implementations

impl<FF> Add<Polynomial<'_, FF>> for Polynomial<'_, FF>

where FF: FiniteField + 'static,

type Output = Polynomial<'static, FF>

The resulting type after applying the + operator.

fn add(self, other: Polynomial<'_, FF>) -> Self::Output

Performs the + operation.

impl<FF: FiniteField> AddAssign<Polynomial<'_, FF>> for Polynomial<'_, FF>

fn add_assign(&mut self, rhs: Polynomial<'_, FF>)

Performs the += operation.

impl<'a, FF> Arbitrary<'a> for Polynomial<'static, FF>

where FF: FiniteField + Arbitrary<'a>,

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

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

fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self, Error>

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<T> BFieldCodec for Polynomial<'_, T>

where T: BFieldCodec + FiniteField + 'static,

type Error = PolynomialBFieldCodecError

fn decode(sequence: &[BFieldElement]) -> Result<Box<Self>, Self::Error>

fn encode(&self) -> Vec<BFieldElement>

fn static_length() -> Option<usize>

Returns the length in number of BFieldElements if it is known at compile-time. Otherwise, None.

impl<'coeffs, FF: Clone + FiniteField> Clone for Polynomial<'coeffs, FF>

fn clone(&self) -> Polynomial<'coeffs, 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> Div<Polynomial<'_, FF>> for Polynomial<'_, FF>

where FF: FiniteField + 'static,

type Output = Polynomial<'static, FF>

The resulting type after applying the / operator.

fn div(self, other: Polynomial<'_, FF>) -> Self::Output

Performs the / operation.

impl<'c, FF> From<&'c [FF]> for Polynomial<'c, FF>

where FF: FiniteField,

fn from(coefficients: &'c [FF]) -> Self

Converts to this type from the input type.

impl<const N: usize, FF, E> From<[E; N]> for Polynomial<'static, 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<'static, 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<'static, BFieldElement>

fn from(xfe: 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, FF2> Mul<Polynomial<'_, FF>> for BFieldElement

where FF: FiniteField + Mul<BFieldElement, Output = FF2>, FF2: 'static + FiniteField,

type Output = Polynomial<'static, FF2>

The resulting type after applying the * operator.

fn mul(self, other: Polynomial<'_, FF>) -> Self::Output

Performs the * operation.

impl<FF, FF2> Mul<Polynomial<'_, FF>> for XFieldElement

where FF: FiniteField + Mul<XFieldElement, Output = FF2>, FF2: 'static + FiniteField,

type Output = Polynomial<'static, FF2>

The resulting type after applying the * operator.

fn mul(self, other: Polynomial<'_, FF>) -> Self::Output

Performs the * operation.

impl<FF, FF2> Mul<Polynomial<'_, FF2>> for Polynomial<'_, FF>

where FF: FiniteField + Mul<FF2>, FF2: FiniteField, <FF as Mul<FF2>>::Output: 'static + FiniteField,

type Output = Polynomial<'static, <FF as Mul<FF2>>::Output>

The resulting type after applying the * operator.

fn mul( self, other: Polynomial<'_, FF2>, ) -> Polynomial<'static, <FF as Mul<FF2>>::Output>

Performs the * operation.

impl<S, FF, FF2> Mul<S> for Polynomial<'_, FF>

where S: FiniteField, FF: FiniteField + Mul<S, Output = FF2>, FF2: 'static + FiniteField,

type Output = Polynomial<'static, FF2>

The resulting type after applying the * operator.

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

Performs the * operation.

impl<FF> Neg for Polynomial<'_, FF>

where FF: FiniteField + 'static,

type Output = Polynomial<'static, FF>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<FF: FiniteField> One for Polynomial<'static, 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: &Polynomial<'_, FF>) -> 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<FF> Rem<Polynomial<'_, FF>> for Polynomial<'_, FF>

where FF: FiniteField + 'static,

type Output = Polynomial<'static, FF>

The resulting type after applying the % operator.

fn rem(self, other: Polynomial<'_, FF>) -> Self::Output

Performs the % operation.

impl<FF> Sub<Polynomial<'_, FF>> for Polynomial<'_, FF>

where FF: FiniteField + 'static,

type Output = Polynomial<'static, FF>

The resulting type after applying the - operator.

fn sub(self, other: Polynomial<'_, FF>) -> Self::Output

Performs the - operation.

impl<FF: FiniteField> Zero for Polynomial<'static, 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>