Trait FftParameters

pub trait FftParameters:
    Sized
    + 'static
    + Send
    + Sync {
    type BigInteger: BigInteger;

    const TWO_ADICITY: u32;
    const TWO_ADIC_ROOT_OF_UNITY: Self::BigInteger;
    const POWERS_OF_ROOTS_OF_UNITY: &'static [Self::BigInteger];
    const SMALL_SUBGROUP_BASE: Option<u32> = None;
    const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = None;
    const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self::BigInteger> = None;
}

A trait that defines parameters for a field that can be used for FFTs.

Required Associated Constants

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. 2^s * t = MODULUS - 1 with t odd. This is the two-adicity of the prime.

const TWO_ADIC_ROOT_OF_UNITY: Self::BigInteger

2^s root of unity, defined as GENERATOR^t.

const POWERS_OF_ROOTS_OF_UNITY: &'static [Self::BigInteger]

TWO_ADIC_ROOT_OF_UNITY^2^i for i := 0..TWO_ADICITY-1

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::BigInteger> = None

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

Required Associated Types

type BigInteger: BigInteger

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.

Implementations on Foreign Types

impl FftParameters for FqParameters

const POWERS_OF_ROOTS_OF_UNITY: &'static [BigInteger384]

const TWO_ADICITY: u32 = 46u32

const TWO_ADIC_ROOT_OF_UNITY: BigInteger384

type BigInteger = BigInteger384

impl FftParameters for FrParameters

const TWO_ADIC_ROOT_OF_UNITY: BigInteger256

TWO_ADIC_ROOT_OF_UNITY = 8065159656716812877374967518403273466521432693661810619979959746626482506078 Encoded in Montgomery form, the value is (8065159656716812877374967518403273466521432693661810619979959746626482506078 * R % q) = 7039866554349711480672062101017509031917008525101396696252683426045173093960

const POWERS_OF_ROOTS_OF_UNITY: &'static [BigInteger256]

const TWO_ADICITY: u32 = 47u32

type BigInteger = BigInteger256

impl FftParameters for FrParameters

const TWO_ADICITY: u32 = 1u32

const TWO_ADIC_ROOT_OF_UNITY: BigInteger256

type BigInteger = BigInteger256

Implementors