Trait 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).

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.

Implementors

impl<P: CubicExtConfig> FftField for CubicExtField<P>

where P::BaseField: FftField,

const GENERATOR: Self = _

const TWO_ADICITY: u32 = <P::BaseField>::TWO_ADICITY

const TWO_ADIC_ROOT_OF_UNITY: Self = _

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

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

const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self> = _

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

impl<P: QuadExtConfig> FftField for QuadExtField<P>

where P::BaseField: FftField,

const GENERATOR: Self = _

const TWO_ADICITY: u32 = <P::BaseField>::TWO_ADICITY

const TWO_ADIC_ROOT_OF_UNITY: Self = _

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

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

const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self> = _