Struct Polynomial 

pub struct Polynomial<F: PrimeField + Ord> { /* private fields */ }

A polynomial expressed as an array of scalar coefficients in ascending degree order (i.e. the first coefficient is the constant term).

Implementations

impl<F: PrimeField + Ord> Polynomial<F>

pub fn with_coefficients(coefficients: Vec<F>) -> Self

Constructs a polynomial with the provided coefficients, which must be in ascending degree order.

pub fn constant(y: F) -> Self

Returns a zero-degree polynomial that evaluates to y everywhere.

pub fn interpolate(points: &[(F, F)]) -> Result<Self>

Constructs a polynomial that interpolates the given points using Lagrange interpolation.

The points are specified as (x, y) pairs.

Running time: O(N^2).

pub fn from_roots(roots: &[F], blinding_factor: F) -> Result<Self>

Interpolates a polynomial that has the given roots.

This algorithm is roughly twice faster than simply calling interpolate with 0 as the y coordinate of all points.

NOTE: if the caller’s protocol doesn’t require a blinding factor it can be set to 1. Do NOT set it to 0, as that would nullify the whole polynomial.

Running time: O(N^2).

pub fn encode2(values: Vec<F>) -> Self

Interpolates a polynomial that encodes an ordered list of values.

The returned polynomial evaluates to the provided values at certain powers of F::ROOT_OF_UNITY. The exact coordinates can be retrieved by calling domain_element2 with the index of the value to query and the size of the domain (i.e. values.len()).

NOTE: this function is called encode2 because it uses the two-adic evaluation domain. For the three-adic version see encode3 below.

Under the hood we use the two-adic Inverse Fourier Transform algorithm (ifft2), which requires the size of the list to be a power of two. If that’s not the case, this function will automatically pad the provided list with zeros.

Additionally, the provided list must not exceed the FFT capacity so it’s required to have no more than 2^(F::S) elements.

Running time: O(N*logN).

pub fn decode2(self) -> Vec<F>

Recovers the ordered list of values encoded by encode2.

This is the inverse of encode2: given a polynomial produced by encode2(values), calling decode2 returns a list equal to values (possibly padded with trailing zeros to the next power of two).

Under the hood we use the two-adic Fast Fourier Transform algorithm (fft2). The polynomial’s coefficient list is zero-padded to the next power of two before the transform is applied.

Running time: O(N*logN).

pub fn len(&self) -> usize

Returns the number of coefficients, which is equal to the maximum degree plus 1.

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

Returns the coefficients of the polynomial in ascending degree order.

pub fn degree_bound(&self) -> usize

Returns the degree bound of the polynomial, ie. the smallest number d such that the degree is strcitly less than d.

Equivalently: this function returns the degree plus one.

Running time: O(N) due to the possibility that some of the trailing coefficients are zero.

pub fn trim(&mut self)

Removes any trailing null coefficients.

After this call, len() is guaranteed to reflect the actual degree bound of the polynomial:

poly.trim(); assert_eq!(poly.len(), poly.degree_bound());

pub fn pad(&mut self, min_degree_bound: usize)

Pads the polynomial with null coefficients until the degree bound is at least degree_bound.

pub fn take(self) -> Vec<F>

Extracts the array of coefficients from this polynomial.

NOTE: the coefficients are in ascending degree order, i.e. the first returned element is the constant term.

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

Multiplies two polynomials. Panics if the FFT capacity is exceeded – that is, if the degree of the product is greater than or equal to 2^(F::S).

pub fn multiply_many<const N: usize>(polynomials: [Self; N]) -> Self

Multiplies two or more polynomials, returning an error if the FFT capacity is exceeded – that is, if the degree of the product is greater than or equal to 2^(F::S).

REQUIRES: the polynomials array must have at least 1 element, otherwise the function will panic.

pub fn multiply_values2(lhs: Vec<F>, rhs: Vec<F>) -> Vec<F>

Multiplies two polynomials defined on the value domain, assuming the provided evaluations are defined on the same two-adic evaluation domain for both.

REQUIRES: the LHS and RHS must have the same length n and it must be a power of two. The implied evaluation domain is the set of powers of an n-th root of unity.

The returned polynomial is also on the value domain and can be switched to the coefficient domain by constructing a Polynomial object on it (see encode2).

pub fn horner(&self, z: F) -> (Self, F)

Divides this polynomial by (x - z) using Horner’s method. Returns the quotient polynomial and the remainder scalar.

Running time: O(N).

pub fn divide_by_zero(&self, n: usize) -> Result<Self>

Divides this polynomial by (x^n - 1), succeeding only if the remainder is 0. The polynomial wrapped in a successful result is the quotient Q such that Q(x) * (x^n - 1) equals this polynomial.

Note that (x^n - 1) is a polynomial that evaluates to zero across an evaluation domain of size n, because the roots of it are the n-th roots of unity. We call this the “zero polynomial”.

NOTE: this algorithm doesn’t check that n is a power of 2 and will work with arbitrary values of n, but it’s generally most useful when n is a power of 2.

Running time: O(N).

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

Evaluates the polynomial at the specified X coordinate.

Running time: O(N).

NOTE: the returned value is the same as the remainder value returned by the horner algorithm above. Even though the two algorithms have the same asymptotic running time, this one is faster because it doesn’t allocate memory for the quotient polynomial.

pub fn domain_element2(index: usize, domain_size: usize) -> F

Returns the X coordinate of the i-th element of a list encoded with encode2.

The returned value is suitable for use with evaluate to query the original value from the encoded list.

domain_size is the length of the original list. It will be rounded up to the next power of two automatically.

Running time: O(1).

pub fn coset_element2(index: usize, domain_size: usize) -> F

Returns the X coordinate of the i-th point in the coset LDE domain used by shifted_lde2.

Equivalent to F::MULTIPLICATIVE_GENERATOR * domain_element2(index, domain_size).

Running time: O(1).

pub fn evaluate_on_two_adic_domain(&self, index: usize, domain_size: usize) -> F

Same as evaluate(domain_element2(index, domain_size)).

Running time: O(N).

pub fn evaluate_on_two_adic_coset(&self, index: usize, domain_size: usize) -> F

Same as evaluate(coset_element2(index, domain_size)).

Running time: O(N).

pub fn shifted_lde2(self, m: usize) -> Vec<F>

Computes a low-degree extension of the polynomial by evaluating it at m points on the coset shift * <omega_m>, where omega_m is a primitive m-th root of unity and shift is the multiplicative generator of the field, F::MULTIPLICATIVE_GENERATOR. The evaluation points are shift * omega_m^i for i = 0..m.

The algorithm shifts the evaluation domain so that the resulting values can be used in (DEEP-)FRI without revealing any of the original values. The coset shift is applied by multiplying each coefficient a_k by F::MULTIPLICATIVE_GENERATOR^k before the FFT, which is equivalent to substituting X -> shift * X in the polynomial.

REQUIRES: m must be a power of two at least as large as self.len(), and no larger than 2^(F::S).

Running time: O(M*log(M)).

impl<F: PrimeField + Ord + ThreeAdicField> Polynomial<F>

pub fn encode3(values: Vec<F>) -> Self

Interpolates a polynomial that encodes an ordered list of values.

The returned polynomial evaluates to the provided values at certain powers of the F::THREE_ADIC_ROOT_OF_UNITY. The exact coordinates can be retrieved by calling domain_element3 with the index of the value to query and the size of the domain (i.e. values.len()).

NOTE: this function is called encode3 because it uses the three-adic evaluation domain. For the two-adic version see encode2 above.

Under the hood we use the three-adic Inverse Fourier Transform algorithm (ifft3), which requires the size of the list to be a power of three. If that’s not the case, this function will automatically pad the provided list with zeros.

Additionally, the provided list must not exceed the FFT capacity so it’s required to have no more than 3^(F::T) elements.

Running time: O(N*logN).

pub fn decode3(self) -> Vec<F>

Recovers the ordered list of values encoded by encode3.

This is the inverse of encode3: given a polynomial produced by encode3(values), calling decode3 returns a list equal to values (possibly padded with trailing zeros to the next power of three).

Under the hood we use the three-adic Fast Fourier Transform algorithm (fft3). The polynomial’s coefficient list is zero-padded to the next power of three before the transform is applied.

Running time: O(N*logN).

pub fn domain_element3(index: usize, domain_size: usize) -> F

Returns the X coordinate of the i-th element of a list encoded with encode3.

The returned value is suitable for use with evaluate to query the original value from the encoded list.

domain_size is the length of the original list. It will be rounded up to the next power of three automatically.

Running time: O(1).

pub fn coset_element3(index: usize, domain_size: usize) -> F

Returns the X coordinate of the i-th point in the coset LDE domain used by shifted_lde3.

Equivalent to F::MULTIPLICATIVE_GENERATOR * domain_element3(index, domain_size).

Running time: O(1).

pub fn evaluate_on_three_adic_domain( &self, index: usize, domain_size: usize, ) -> F

Same as evaluate(domain_element3(index, domain_size)).

Running time: O(N).

pub fn evaluate_on_three_adic_coset( &self, index: usize, domain_size: usize, ) -> F

Same as evaluate(coset_element3(index, domain_size)).

Running time: O(N).

pub fn shifted_lde3(self, m: usize) -> Vec<F>

Computes a low-degree extension of the polynomial by evaluating it at m points on the coset shift * <omega_m>, where omega_m is a primitive m-th root of unity and shift is the multiplicative generator of the field, F::MULTIPLICATIVE_GENERATOR. The evaluation points are shift * omega_m^i for i = 0..m.

The algorithm shifts the evaluation domain so that the resulting values can be used in (DEEP-)FRI without revealing any of the original values. The coset shift is applied by multiplying each coefficient a_k by F::MULTIPLICATIVE_GENERATOR^k before the FFT, which is equivalent to substituting X -> shift * X in the polynomial.

REQUIRES: m must be a power of three at least as large as self.len(), and no larger than 3^(F::T).

Running time: O(M*log(M)).

pub fn multiply_values3(lhs: Vec<F>, rhs: Vec<F>) -> Vec<F>

Multiplies two polynomials defined on the value domain, assuming the provided evaluations are defined on the same three-adic evaluation domain for both.

REQUIRES: the LHS and RHS must have the same length n and it must be a power of three. The implied evaluation domain is the set of powers of an n-th root of unity.

The returned polynomial is also on the value domain and can be switched to the coefficient domain by constructing a Polynomial object on it (see encode3).

Trait Implementations

impl<F: PrimeField + Ord> Add<F> for Polynomial<F>

type Output = Polynomial<F>

The resulting type after applying the + operator.

fn add(self, rhs: F) -> Self::Output

Performs the + operation.

impl<F: PrimeField + Ord> Add for Polynomial<F>

type Output = Polynomial<F>

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self::Output

Performs the + operation.

impl<F: PrimeField + Ord> AddAssign<F> for Polynomial<F>

fn add_assign(&mut self, rhs: F)

Performs the += operation.

impl<F: PrimeField + Ord> AddAssign for Polynomial<F>

fn add_assign(&mut self, rhs: Self)

Performs the += operation.

impl<F: Clone + PrimeField + Ord> Clone for Polynomial<F>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<F: Debug + PrimeField + Ord> Debug for Polynomial<F>

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

Formats the value using the given formatter.

impl<F: Default + PrimeField + Ord> Default for Polynomial<F>

fn default() -> Polynomial<F>

Returns the “default value” for a type.

impl<F: PrimeField + Ord> Mul<F> for Polynomial<F>

type Output = Polynomial<F>

The resulting type after applying the * operator.

fn mul(self, rhs: F) -> Self::Output

Performs the * operation.

impl<F: PrimeField + Ord> Mul for Polynomial<F>

type Output = Polynomial<F>

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Self::Output

Performs the * operation.

impl<F: PrimeField + Ord> MulAssign<F> for Polynomial<F>

fn mul_assign(&mut self, rhs: F)

Performs the *= operation.

impl<F: PrimeField + Ord> MulAssign for Polynomial<F>

fn mul_assign(&mut self, rhs: Self)

Performs the *= operation.

impl<F: PrimeField + Ord> Neg for Polynomial<F>

type Output = Polynomial<F>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<F: PartialEq + PrimeField + Ord> PartialEq for Polynomial<F>

fn eq(&self, other: &Polynomial<F>) -> 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: PrimeField + Ord> Sub<F> for Polynomial<F>

type Output = Polynomial<F>

The resulting type after applying the - operator.

fn sub(self, rhs: F) -> Self::Output

Performs the - operation.

impl<F: PrimeField + Ord> Sub for Polynomial<F>

type Output = Polynomial<F>

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self::Output

Performs the - operation.

impl<F: PrimeField + Ord> SubAssign<F> for Polynomial<F>

fn sub_assign(&mut self, rhs: F)

Performs the -= operation.

impl<F: PrimeField + Ord> SubAssign for Polynomial<F>

fn sub_assign(&mut self, rhs: Self)

Performs the -= operation.

impl<F: Eq + PrimeField + Ord> Eq for Polynomial<F>

impl<F: PrimeField + Ord> StructuralPartialEq for Polynomial<F>