Struct ark_poly::domain::mixed_radix::MixedRadixEvaluationDomain

pub struct MixedRadixEvaluationDomain<F: FftField> {
    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 generator_inv: F,
}

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

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.

generator_inv: F

Multiplicative generator of the finite field.

Trait Implementations

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

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

Reads Self from reader.

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

Reads Self from reader without compression.

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

Reads self from reader without compression, and without performing validity checks. Should be used only when the input is trusted.

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

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

Serializes self into writer. It is left up to a particular type for how it strikes the serialization efficiency vs compression tradeoff. For standard types (e.g. bool, lengths, etc.) typically an uncompressed form is used, whereas for algebraic types compressed forms are used.

fn serialized_size(&self) -> usize

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

Serializes self into writer without compression.

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

Serializes self into writer without compression, and without performing validity checks. Should be used only when there is no danger of adversarial manipulation of the output.

fn uncompressed_size(&self) -> usize

impl<F: Clone + FftField> Clone for MixedRadixEvaluationDomain<F>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<F: Copy + FftField> Copy for MixedRadixEvaluationDomain<F>

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

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

Formats the value using the given formatter.

impl<F: Eq + FftField> Eq for MixedRadixEvaluationDomain<F>

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

type Elements = Elements<F>

The type of the elements iterator.

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

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

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 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 coset_ifft_in_place<T: DomainCoeff<F>>(&self, evals: &mut Vec<T>)

Compute a IFFT over a coset of the domain, modifying the input vector in place.

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. For multiplicative subgroups, this polynomial is z(X) = X^self.size - 1.

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

Returns the i-th element of the domain, where elements are ordered by their power of the generator which they correspond to. e.g. the i-th element is g^i

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

Return an iterator over the elements of the domain.

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

Sample an element that is not in the domain.

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 coset_fft<T: DomainCoeff<F>>(&self, coeffs: &[T]) -> Vec<T>

Compute a FFT over a coset of the domain.

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

Compute a FFT over a coset of the domain, modifying the input vector in place.

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

Compute a IFFT over a coset of the domain.

fn divide_by_vanishing_poly_on_coset_in_place(&self, evals: &mut [F])

The target polynomial is the zero polynomial in our evaluation domain, so we must perform division over a coset.

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.

#[must_use]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 + FftField> Hash for MixedRadixEvaluationDomain<F>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

pub fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl<F: PartialEq + FftField> PartialEq<MixedRadixEvaluationDomain<F>> for MixedRadixEvaluationDomain<F>

fn eq(&self, other: &MixedRadixEvaluationDomain<F>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &MixedRadixEvaluationDomain<F>) -> bool

This method tests for !=.

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

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