Struct Radix2EvaluationDomain 

pub struct Radix2EvaluationDomain<F: Field> {
    pub size: u64,
    pub log_size_of_group: u32,
    pub size_as_field_element: F,
    pub size_inv: F,
    pub group_gen: F,
    pub group_gen_inv: F,
    pub offset: F,
    pub offset_inv: F,
    pub offset_pow_size: F,
}

Defines a domain over which finite field (I)FFTs can be performed. Works only for fields that have a large multiplicative subgroup of size that is a power-of-2.

Fields

size: u64

The size of the domain.

log_size_of_group: u32

log_2(self.size).

size_as_field_element: F

Size of the domain as a field element.

size_inv: F

Inverse of the size in the field.

group_gen: F

A generator of the subgroup.

group_gen_inv: F

Inverse of the generator of the subgroup.

offset: F

Offset that specifies the coset.

offset_inv: F

Inverse of the offset that specifies the coset.

offset_pow_size: F

Constant coefficient for the vanishing polynomial. Equals self.offset^self.size.

Trait Implementations

impl<F: Field> CanonicalDeserialize for Radix2EvaluationDomain<F>

fn deserialize_with_mode<R: Read>( reader: R, compress: Compress, validate: Validate, ) -> Result<Self, SerializationError>

The general deserialize method that takes in customization flags.

fn deserialize_compressed<R>(reader: R) -> Result<Self, SerializationError>

where R: Read,

Reads Self from reader using the compressed form if applicable. Performs validation if applicable.

fn deserialize_compressed_unchecked<R>( reader: R, ) -> Result<Self, SerializationError>

where R: Read,

Reads Self from reader using the compressed form if applicable, without validating the deserialized value.

fn deserialize_uncompressed<R>(reader: R) -> Result<Self, SerializationError>

where R: Read,

Reads Self from reader using the uncompressed form. Performs validation if applicable.

fn deserialize_uncompressed_unchecked<R>( reader: R, ) -> Result<Self, SerializationError>

where R: Read,

Reads Self from reader using the uncompressed form, without validating the deserialized value.

impl<F: Field> CanonicalSerialize for Radix2EvaluationDomain<F>

fn serialize_with_mode<W: Write>( &self, writer: W, compress: Compress, ) -> Result<(), SerializationError>

The general serialize method that takes in customization flags.

fn serialized_size(&self, compress: Compress) -> usize

Returns the size in bytes of the serialized version of self with the given compression mode.

fn serialize_compressed<W>(&self, writer: W) -> Result<(), SerializationError>

where W: Write,

Serializes self into writer using the compressed form if applicable.

fn compressed_size(&self) -> usize

Returns the size in bytes of the compressed serialized version of self.

fn serialize_uncompressed<W>(&self, writer: W) -> Result<(), SerializationError>

where W: Write,

Serializes self into writer using the uncompressed form.

fn uncompressed_size(&self) -> usize

Returns the size in bytes of the uncompressed serialized version of self.

impl<F: Clone + Field> Clone for Radix2EvaluationDomain<F>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<F: Field> Debug for Radix2EvaluationDomain<F>

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

Formats the value using the given formatter.

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

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

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

fn elements(&self) -> Elements<F>

Return an iterator over the elements of the domain.

type Elements = Elements<F>

The type of the elements iterator.

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 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.

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.

impl<F: Hash + Field> Hash for Radix2EvaluationDomain<F>

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<F: PartialEq + Field> PartialEq for Radix2EvaluationDomain<F>

fn eq(&self, other: &Radix2EvaluationDomain<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: Field> Valid for Radix2EvaluationDomain<F>

const TRIVIAL_CHECK: bool

Whether the check method is trivial (i.e. always returns Ok(())). If this is true, the batch_check method will skip all checks and return Ok(()). This should be set to true for types where check is trivial, e.g. integers, field elements, etc. This is false by default. This is primarily an optimization to skip unnecessary checks in batch_check.

fn check(&self) -> Result<(), SerializationError>

Checks whether self is valid. If self is valid, returns Ok(()). Otherwise, returns an error describing the failure. This method is called by deserialize_with_mode if validate is Validate::Yes.

fn batch_check<'a>( batch: impl Iterator<Item = &'a Self> + Send, ) -> Result<(), SerializationError>

where Self: 'a,

Checks whether all items in batch are valid. If all items are valid, returns Ok(()). Otherwise, returns an error describing the first failure.

impl<F: Copy + Field> Copy for Radix2EvaluationDomain<F>

impl<F: Eq + Field> Eq for Radix2EvaluationDomain<F>

impl<F: Field> StructuralPartialEq for Radix2EvaluationDomain<F>