Trait ark_ff::fields::FftField

pub trait FftField: Field {
    const GENERATOR: Self;
    const TWO_ADICITY: u32;
    const TWO_ADIC_ROOT_OF_UNITY: Self;
    const SMALL_SUBGROUP_BASE: Option<u32> = None;
    const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = None;
    const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self> = None;

    // Provided method
    fn get_root_of_unity(n: u64) -> Option<Self> { ... }
}

The interface for fields that are able to be used in FFTs.

Required Associated Constants

const GENERATOR: Self

The generator of the multiplicative group of the field

const TWO_ADICITY: u32

Let N be the size of the multiplicative group defined by the field. Then TWO_ADICITY is the two-adicity of N, i.e. the integer s such that N = 2^s * t for some odd integer t.

const TWO_ADIC_ROOT_OF_UNITY: Self

2^s root of unity computed by GENERATOR^t

Provided Associated Constants

const SMALL_SUBGROUP_BASE: Option<u32> = None

An integer b such that there exists a multiplicative subgroup of size b^k for some integer k.

const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = None

The integer k such that there exists a multiplicative subgroup of size Self::SMALL_SUBGROUP_BASE^k.

const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self> = None

GENERATOR^((MODULUS-1) / (2^s * SMALL_SUBGROUP_BASE^SMALL_SUBGROUP_BASE_ADICITY)) Used for mixed-radix FFT.

Provided Methods

fn get_root_of_unity(n: u64) -> Option<Self>

Returns the root of unity of order n, if one exists. If no small multiplicative subgroup is defined, this is the 2-adic root of unity of order n (for n a power of 2). If a small multiplicative subgroup is defined, this is the root of unity of order n for the larger subgroup generated by FftConfig::LARGE_SUBGROUP_ROOT_OF_UNITY (for n = 2^i * FftConfig::SMALL_SUBGROUP_BASE^j for some i, j).

Implementors

impl<P: FpConfig<N>, const N: usize> FftField for Fp<P, N>

const GENERATOR: Self = P::GENERATOR

const TWO_ADICITY: u32 = P::TWO_ADICITY

const TWO_ADIC_ROOT_OF_UNITY: Self = P::TWO_ADIC_ROOT_OF_UNITY

const SMALL_SUBGROUP_BASE: Option<u32> = P::SMALL_SUBGROUP_BASE

const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = P::SMALL_SUBGROUP_BASE_ADICITY

const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self> = P::LARGE_SUBGROUP_ROOT_OF_UNITY