pub trait IsFFTField: IsField {
const TWO_ADICITY: u64;
const TWO_ADIC_PRIMITVE_ROOT_OF_UNITY: Self::BaseType;
// Provided methods
fn field_name() -> &'static str { ... }
fn get_primitive_root_of_unity(
order: u64,
) -> Result<FieldElement<Self>, FieldError> { ... }
}Expand description
Trait to define necessary parameters for FFT-friendly Fields.
Two-Adic fields are ones whose order is of the form $2^n k + 1$.
Here $n$ is usually called the two-adicity of the field. The
reason we care about it is that in an $n$-adic field there are $2^j$-roots
of unity for every j between 1 and n, which is needed to do Fast Fourier.
A two-adic primitive root of unity is a number w that satisfies w^(2^n) = 1
and w^(j) != 1 for every j below 2^n. With this primitive root we can generate
any other root of unity we need to perform FFT.
Required Associated Constants§
const TWO_ADICITY: u64
const TWO_ADIC_PRIMITVE_ROOT_OF_UNITY: Self::BaseType
Provided Methods§
Sourcefn field_name() -> &'static str
fn field_name() -> &'static str
Used for searching this field’s implementation in other languages, e.g in MSL for executing parallel operations with the Metal API.
Sourcefn get_primitive_root_of_unity(
order: u64,
) -> Result<FieldElement<Self>, FieldError>
fn get_primitive_root_of_unity( order: u64, ) -> Result<FieldElement<Self>, FieldError>
Returns a primitive root of unity of order $2^{order}$.
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.