Skip to main content

AdditiveNtt

p3_binary_dft

Trait AdditiveNtt 

Source 
pub trait AdditiveNtt<F: TowerLevel> {
    // Required methods
    fn shifted_ntt_batch(
        &self,
        mat: RowMajorMatrix<F>,
        shift: F,
    ) -> RowMajorMatrix<F>;
    fn shifted_intt_batch(
        &self,
        mat: RowMajorMatrix<F>,
        shift: F,
    ) -> RowMajorMatrix<F>;

    // Provided methods
    fn ntt_batch(&self, mat: RowMajorMatrix<F>) -> RowMajorMatrix<F> { ... }
    fn intt_batch(&self, mat: RowMajorMatrix<F>) -> RowMajorMatrix<F> { ... }
    fn lde_batch(
        &self,
        mat: RowMajorMatrix<F>,
        added_bits: usize,
    ) -> RowMajorMatrix<F> { ... }
    fn shifted_lde_batch(
        &self,
        mat: RowMajorMatrix<F>,
        added_bits: usize,
        shift: F,
    ) -> RowMajorMatrix<F> { ... }
}
Expand description

An additive NTT: evaluation of the novel polynomial basis on an F_2-linear subspace.

Columns hold coefficients in the novel polynomial basis X_i = ∏_j Ŵ_j^{bit_j(i)}, the products of normalised subspace polynomials; output row i is the evaluation at shift + domain_point(i). Both sides are in natural order.

Heights are powers of two, and ℓ = log2(height) is at most the bit width 2^LOG_BITS of F: S_ℓ is spanned by the first ℓ Cantor basis vectors, of which there are only that many.

No Clone + Default supertrait: an implementation carrying state — a precomputed twiddle table, a configurable grain, a non-Cantor subspace basis — should not be ruled out by the interface. AdditiveRsEncoder requires those bounds itself.

Required Methods§

Source

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

Evaluates each column on the coset shift + S_ℓ.

§Panics

Panics if the height of mat is not a power of two, or if ℓ exceeds the bit width of F, since S_ℓ then calls for a Cantor basis vector this level does not have.

Source

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

Inverse of shifted_ntt_batch.

§Panics

Panics under the same conditions as shifted_ntt_batch.

Provided Methods§

Source

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

Evaluates each column on S_ℓ.

Source

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

Inverse of ntt_batch.

Source

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

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

Because S_ℓ is the index prefix of the larger domain, the input rows reappear as the prefix of the output.

§Panics

Panics unless ℓ + added_bits is at most the bit width of F, on top of the conditions of shifted_ntt_batch.

Source

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

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

Dyn Compatibility§

This trait is dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors§