Module domain

This module contains an EvaluationDomain abstraction for performing various kinds of polynomial arithmetic on top of fields that are friendly to fast-fourier-transforms (FFTs).

A field is FFT-friendly if it contains enough roots of unity to perform the FFT in O(n log n) time. These roots of unity comprise the domain over which polynomial arithmetic is performed.

Re-exports

pub use general::GeneralEvaluationDomain;

pub use mixed_radix::MixedRadixEvaluationDomain;

pub use radix2::Radix2EvaluationDomain;

Modules

general

This module contains a GeneralEvaluationDomain for performing various kinds of polynomial arithmetic on top of a FFT-friendly finite field.

mixed_radix

This module contains a MixedRadixEvaluationDomain for performing various kinds of polynomial arithmetic on top of fields that are FFT-friendly but do not have high-enough two-adicity to perform the FFT efficiently, i.e. the multiplicative subgroup G generated by F::TWO_ADIC_ROOT_OF_UNITY is not large enough. MixedRadixEvaluationDomain resolves this issue by using a larger subgroup obtained by combining G with another subgroup of size F::SMALL_SUBGROUP_BASE^(F::SMALL_SUBGROUP_BASE_ADICITY), to obtain a subgroup generated by F::LARGE_SUBGROUP_ROOT_OF_UNITY.

radix2

This module defines Radix2EvaluationDomain, an EvaluationDomain for performing various kinds of polynomial arithmetic on top of fields that are FFT-friendly. Radix2EvaluationDomain supports FFTs of size at most 2^F::TWO_ADICITY.

Traits

DomainCoeff

Types that can be FFT-ed must implement this trait.

EvaluationDomain

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.