Trait EvaluationDomain

pub trait EvaluationDomain<F: FftField>:
    Copy
    + Clone
    + Hash
    + Eq
    + PartialEq
    + Debug
    + CanonicalSerialize
    + CanonicalDeserialize {
    type Elements: Iterator<Item = F> + Sized;

    // Required methods
    fn new(num_coeffs: usize) -> Option<Self>;
    fn get_coset(&self, offset: F) -> Option<Self>;
    fn compute_size_of_domain(num_coeffs: usize) -> Option<usize>;
    fn size(&self) -> usize;
    fn log_size_of_group(&self) -> u64;
    fn size_inv(&self) -> F;
    fn group_gen(&self) -> F;
    fn group_gen_inv(&self) -> F;
    fn coset_offset(&self) -> F;
    fn coset_offset_inv(&self) -> F;
    fn coset_offset_pow_size(&self) -> F;
    fn fft_in_place<T: DomainCoeff<F>>(&self, coeffs: &mut Vec<T>);
    fn ifft_in_place<T: DomainCoeff<F>>(&self, evals: &mut Vec<T>);
    fn elements(&self) -> Self::Elements;

    // Provided methods
    fn sample_element_outside_domain<R: Rng>(&self, rng: &mut R) -> F { ... }
    fn new_coset(num_coeffs: usize, offset: F) -> Option<Self> { ... }
    fn size_as_field_element(&self) -> F { ... }
    fn fft<T: DomainCoeff<F>>(&self, coeffs: &[T]) -> Vec<T> { ... }
    fn ifft<T: DomainCoeff<F>>(&self, evals: &[T]) -> Vec<T> { ... }
    fn distribute_powers<T: DomainCoeff<F>>(coeffs: &mut [T], g: F) { ... }
    fn distribute_powers_and_mul_by_const<T: DomainCoeff<F>>(
        coeffs: &mut [T],
        g: F,
        c: F,
    ) { ... }
    fn evaluate_all_lagrange_coefficients(&self, tau: F) -> Vec<F> { ... }
    fn vanishing_polynomial(&self) -> SparsePolynomial<F> { ... }
    fn evaluate_vanishing_polynomial(&self, tau: F) -> F { ... }
    fn filter_polynomial(&self, subdomain: &Self) -> DensePolynomial<F> { ... }
    fn evaluate_filter_polynomial(&self, subdomain: &Self, tau: F) -> F { ... }
    fn element(&self, i: usize) -> F { ... }
    fn reindex_by_subdomain(&self, other: Self, index: usize) -> usize { ... }
    fn mul_polynomials_in_evaluation_domain(
        &self,
        self_evals: &[F],
        other_evals: &[F],
    ) -> Vec<F> { ... }
}

Defines a domain over which finite field (I)FFTs can be performed. The size of the supported FFT depends on the size of the multiplicative subgroup. For efficiency, we recommend that the field has at least one large subgroup generated by a root of unity.

Required Associated Types

type Elements: Iterator<Item = F> + Sized

The type of the elements iterator.

Required Methods

fn new(num_coeffs: usize) -> Option<Self>

Construct a domain that is large enough for evaluations of a polynomial having num_coeffs coefficients.

fn get_coset(&self, offset: F) -> Option<Self>

Construct a coset domain from a subgroup domain

fn compute_size_of_domain(num_coeffs: usize) -> Option<usize>

Return the size of a domain that is large enough for evaluations of a polynomial having num_coeffs coefficients.

fn size(&self) -> usize

Return the size of self.

fn log_size_of_group(&self) -> u64

Return log_2(size) of self.

fn size_inv(&self) -> F

Return the inverse of self.size_as_field_element().

fn group_gen(&self) -> F

Return the generator for the multiplicative subgroup that defines this domain.

fn group_gen_inv(&self) -> F

Return the group inverse of self.group_gen().

fn coset_offset(&self) -> F

Return the group offset that defines this domain.

fn coset_offset_inv(&self) -> F

Return the inverse of self.offset().

fn coset_offset_pow_size(&self) -> F

Return offset^size.

fn fft_in_place<T: DomainCoeff<F>>(&self, coeffs: &mut Vec<T>)

Compute a FFT, modifying the vector in place.

fn ifft_in_place<T: DomainCoeff<F>>(&self, evals: &mut Vec<T>)

Compute a IFFT, modifying the vector in place.

fn elements(&self) -> Self::Elements

Return an iterator over the elements of the domain.

Provided Methods

fn sample_element_outside_domain<R: Rng>(&self, rng: &mut R) -> F

Sample an element that is not in the domain.

fn new_coset(num_coeffs: usize, offset: F) -> Option<Self>

Construct a coset domain that is large enough for evaluations of a polynomial having num_coeffs coefficients.

fn size_as_field_element(&self) -> F

Return the size of self as a field element.

fn fft<T: DomainCoeff<F>>(&self, coeffs: &[T]) -> Vec<T>

Compute a FFT.

fn ifft<T: DomainCoeff<F>>(&self, evals: &[T]) -> Vec<T>

Compute a IFFT.

fn distribute_powers<T: DomainCoeff<F>>(coeffs: &mut [T], g: F)

Multiply the i-th element of coeffs with g^i.

fn distribute_powers_and_mul_by_const<T: DomainCoeff<F>>( coeffs: &mut [T], g: F, c: F, )

Multiply the i-th element of coeffs with c*g^i.

fn evaluate_all_lagrange_coefficients(&self, tau: F) -> Vec<F>

Evaluate all the lagrange polynomials defined by this domain at the point tau. This is computed in time O(|domain|). Then given the evaluations of a degree d polynomial P over this domain, where d < |domain|, P(tau) can be computed as P(tau) = sum_{i in [|Domain|]} L_{i, Domain}(tau) * P(g^i). L_{i, Domain} is the value of the i-th lagrange coefficient in the returned vector.

fn vanishing_polynomial(&self) -> SparsePolynomial<F>

Return the sparse vanishing polynomial.

fn evaluate_vanishing_polynomial(&self, tau: F) -> F

This evaluates the vanishing polynomial for this domain at tau.

fn filter_polynomial(&self, subdomain: &Self) -> DensePolynomial<F>

Return the filter polynomial of self with respect to the subdomain subdomain. Assumes that subdomain is contained within self.

Panics

Panics if subdomain is not contained within self.

fn evaluate_filter_polynomial(&self, subdomain: &Self, tau: F) -> F

This evaluates at tau the filter polynomial for self with respect to the subdomain subdomain.

fn element(&self, i: usize) -> F

Returns the i-th element of the domain.

fn reindex_by_subdomain(&self, other: Self, index: usize) -> usize

Given an index which assumes the first elements of this domain are the elements of another (sub)domain, this returns the actual index into this domain.

fn mul_polynomials_in_evaluation_domain( &self, self_evals: &[F], other_evals: &[F], ) -> Vec<F>

Perform O(n) multiplication of two polynomials that are presented by their evaluations in the domain. Returns the evaluations of the product over the domain.

Assumes that the domain is large enough to allow for successful interpolation after multiplication.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<F: FftField> EvaluationDomain<F> for GeneralEvaluationDomain<F>

type Elements = GeneralElements<F>

impl<F: FftField> EvaluationDomain<F> for MixedRadixEvaluationDomain<F>

type Elements = Elements<F>

impl<F: FftField> EvaluationDomain<F> for Radix2EvaluationDomain<F>

type Elements = Elements<F>