Trait snarkvm_fields::traits::FftField

source · 
pub trait FftField: Field + From<u128> + From<u64> + From<u32> + From<u16> + From<u8> {
    type FftParameters: FftParameters;

    // Required methods
    fn two_adic_root_of_unity() -> Self;
    fn large_subgroup_root_of_unity() -> Option<Self>;
    fn multiplicative_generator() -> Self;

    // Provided methods
    fn get_root_of_unity(n: usize) -> Option<Self> { ... }
    fn k_adicity(k: usize, n: usize) -> u32 { ... }
}
Expand description

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

Required Associated Types§

source

type FftParameters: FftParameters

Required Methods§

source

fn two_adic_root_of_unity() -> Self

Returns the 2^s root of unity.

source

fn large_subgroup_root_of_unity() -> Option<Self>

Returns the 2^s * small_subgroup_base^small_subgroup_base_adicity root of unity if a small subgroup is defined.

source

fn multiplicative_generator() -> Self

Returns the multiplicative generator of char() - 1 order.

Provided Methods§

source

fn get_root_of_unity(n: usize) -> 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 FftParams::LARGE_SUBGROUP_ROOT_OF_UNITY (for n = 2^i * FftParams::SMALL_SUBGROUP_BASE^j for some i, j).

source

fn k_adicity(k: usize, n: usize) -> u32

Calculates the k-adicity of n, i.e., the number of trailing 0s in a base-k representation.

Object Safety§

This trait is not object safe.

Implementors§