Trait FieldNTT 

pub trait FieldNTT: Field {
    const MAX_LG_ROOT_ORDER: u8;

    // Required methods
    fn root_of_unity(lg: u8) -> Option<Self>;
    fn coset_shift() -> Self;

    // Provided methods
    fn coset_shift_inv() -> Self { ... }
    fn div_2(&self) -> Self { ... }
}

A Field which supports operations allowing for efficient NTTs.

Fields implementing this trait must have characteristic not equal to 2 (so that 2 is invertible), and must have a multiplicative group with sufficiently large 2-adic order.

Required Associated Constants

const MAX_LG_ROOT_ORDER: u8

The maximum (lg) of the power of two root of unity this fields supports.

Required Methods

fn root_of_unity(lg: u8) -> Option<Self>

A root of unity of order 2^lg.

In other words, for r = root_of_unity(lg), k = 2^lg should be the smallest power such that r^k = 1.

This function should return None only for lg > MAX_LG_ROOT_ORDER.

fn coset_shift() -> Self

An element which is not a power of a root of unity.

In other words, for any lg, k, this element should not equal Self::root_of_unity(lg)^k.

Provided Methods

fn coset_shift_inv() -> Self

fn div_2(&self) -> Self

Return the result of dividing this element by 2.

This is equivalent to self * (1 + 1)^-1, but is usually implementable in a more efficient way.

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 FieldNTT for F

const MAX_LG_ROOT_ORDER: u8 = 32