Trait lambdaworks_math::field::traits::IsFFTField

source · 
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§

source

const TWO_ADICITY: u64

source

const TWO_ADIC_PRIMITVE_ROOT_OF_UNITY: Self::BaseType

Provided Methods§

source

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.

source

fn get_primitive_root_of_unity( order: u64, ) -> Result<FieldElement<Self>, FieldError>

Returns a primitive root of unity of order $2^{order}$.

Object Safety§

This trait is not object safe.

Implementors§