Trait scuttlebutt::field::fft::FieldForFFT

pub trait FieldForFFT<const N: usize>: FiniteField + TryFrom<u128> {
    const PHI_EXP: usize;

    fn roots(p: usize) -> Self;
}

This trait indicates that a finite field is suitable for use in radix-N FFT. This means that it must have a power-of-N root of unity for any desired FFT size, i.e., a field element r_p, such that r_p^(N^p) = 1, for a size-3^p FFT. The PHI_EXP constant is the exponent of the largest FFT size supported, and root should return the N^pth root of unity.

Required Associated Constants

const PHI_EXP: usize

Largest integer p such that phi(MODULUS) = N^p * k for integer k.

Required Methods

fn roots(p: usize) -> Self

For each p such that N^p | phi(MODULUS), there is a (N^p)th root of unity, namely r_p = GENERATOR^(phi(MODULUS) / N^p), since then r_p^(N^p) = GENERATOR^phi(MODULUS) = 1. This function should return this r_p, on input p, for p in [0 .. PHI_EXP].

Implementors

impl FieldForFFT<2> for F2e19x3e26

const PHI_EXP: usize = 19usize

impl FieldForFFT<3> for F2e19x3e26

const PHI_EXP: usize = 26usize