Struct LchNtt 

pub struct LchNtt<F> { /* private fields */ }

The Lin–Chung–Han additive NTT over the Cantor-basis domain.

Twiddles are index shifts (D8): at stage j and butterfly block blk the twiddle is W_j(shift) + domain_point(blk << 1), so there is no twiddle table.

Consecutive blocks differ by a fixed increment, so a block takes its twiddle from the one before it rather than walking its own index. The ℓ - 1 increments are shared by every stage and are the only per-size precomputation.

W_j is F_2-linear and domain_point(0) is zero, so over the subspace itself — the coset with shift = 0 — the first block of every stage has a zero twiddle and its butterfly collapses to a single addition. The inner loop takes that as a separate case, which removes one multiply in 2/ℓ of them.

At the wide stages a pair of rows is megabytes apart, so a stage alone costs a pass over memory. The schedule groups adjacent stages into row sets closed under all of them.

Trait Implementations

impl<F: ButterflyField> AdditiveNtt<F> for LchNtt<F>

fn shifted_ntt_batch( &self, mat: RowMajorMatrix<F>, shift: F, ) -> RowMajorMatrix<F>

Evaluates each column on the coset shift + S_ℓ.

fn shifted_intt_batch( &self, mat: RowMajorMatrix<F>, shift: F, ) -> RowMajorMatrix<F>

Inverse of shifted_ntt_batch.

fn ntt_batch_padded( &self, mat: RowMajorMatrix<F>, log_inv_rate: usize, ) -> RowMajorMatrix<F>

Transforms a matrix whose coefficient prefix has been padded with zero rows.

fn ntt_batch(&self, mat: RowMajorMatrix<F>) -> RowMajorMatrix<F>

Evaluates each column on S_ℓ.

fn intt_batch(&self, mat: RowMajorMatrix<F>) -> RowMajorMatrix<F>

Inverse of ntt_batch.

fn lde_batch( &self, mat: RowMajorMatrix<F>, added_bits: usize, ) -> RowMajorMatrix<F>

Low-degree extension onto S_{ℓ + added_bits} ⊃ S_ℓ.

fn shifted_lde_batch( &self, mat: RowMajorMatrix<F>, added_bits: usize, shift: F, ) -> RowMajorMatrix<F>

lde_batch on the coset shift + S_{ℓ + added_bits}.

impl<F: Clone> Clone for LchNtt<F>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<F: Debug> Debug for LchNtt<F>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<F: Default> Default for LchNtt<F>

fn default() -> Self

Returns the “default value” for a type.