Trait AdditiveNTT

pub trait AdditiveNTT<F: BinaryField> {
    // Required methods
    fn log_domain_size(&self) -> usize;
    fn subspace(&self, i: usize) -> BinarySubspace<F>;
    fn get_subspace_eval(&self, i: usize, j: usize) -> F;
    fn forward_transform<P: PackedField<Scalar = F>>(
        &self,
        data: &mut [P],
        shape: NTTShape,
        coset: u32,
        skip_rounds: usize,
    ) -> Result<(), Error>;
    fn inverse_transform<P: PackedField<Scalar = F>>(
        &self,
        data: &mut [P],
        shape: NTTShape,
        coset: u32,
        skip_rounds: usize,
    ) -> Result<(), Error>;

    // Provided methods
    fn forward_transform_ext<PE: PackedExtension<F>>(
        &self,
        data: &mut [PE],
        shape: NTTShape,
        coset: u32,
        skip_rounds: usize,
    ) -> Result<(), Error> { ... }
    fn inverse_transform_ext<PE: PackedExtension<F>>(
        &self,
        data: &mut [PE],
        shape: NTTShape,
        coset: u32,
        skip_rounds: usize,
    ) -> Result<(), Error> { ... }
}

The binary field additive NTT.

A number-theoretic transform (NTT) is a linear transformation on a finite field analogous to the discrete fourier transform. The version of the additive NTT we use is originally described in LCH14. In DP24 Section 3.1, the authors present the LCH additive NTT algorithm in a way that makes apparent its compatibility with the FRI proximity test. Throughout the documentation, we will refer to the notation used in DP24.

The additive NTT is parameterized by a binary field $K$ and $\mathbb{F}_2$-linear subspace. We write $\beta_0, \ldots, \beta_{\ell-1}$ for the ordered basis elements of the subspace and require $\beta_0 = 1$. The basis determines a novel polynomial basis and an evaluation domain. In the forward direction, the additive NTT transforms a vector of polynomial coefficients, with respect to the novel polynomial basis, into a vector of their evaluations over the evaluation domain. The inverse transformation interpolates polynomial values over the domain into novel polynomial basis coefficients.

Required Methods

fn log_domain_size(&self) -> usize

Base-2 logarithm of the maximum size of the NTT domain, $\ell$.

fn subspace(&self, i: usize) -> BinarySubspace<F>

Returns the binary subspace $S^{(i)}$.

The domain will have dimension $\ell - i$.

Preconditions

• i must be less than self.log_domain_size()

fn get_subspace_eval(&self, i: usize, j: usize) -> F

Get the normalized subspace polynomial evaluation $\hat{W}_i(\beta_j)$.

Preconditions

• i must be less than self.log_domain_size()
• j must be less than self.log_domain_size() - i

fn forward_transform<P: PackedField<Scalar = F>>( &self, data: &mut [P], shape: NTTShape, coset: u32, skip_rounds: usize, ) -> Result<(), Error>

Batched forward transformation defined in DP24, Section 2.3.

The scalars of data, viewed in natural order, represent a tensor of shape dimensions. See NTTShape for layout details. The transform is inplace, output adheres to shape.

The coset specifies the evaluation domain as an indexed coset of the subspace.

The transformation accepts a skip_rounds parameter, which is a number of NTT layers to skip at the beginning of the forward transform. This corresponds to parallel NTTs on multiple adjacent subspace cosets, but beginning with messages interpreted as coefficients in a modified novel polynomial basis. See DP24 Remark 4.15.

fn inverse_transform<P: PackedField<Scalar = F>>( &self, data: &mut [P], shape: NTTShape, coset: u32, skip_rounds: usize, ) -> Result<(), Error>

Batched inverse transformation defined in DP24, Section 2.3.

The scalars of data, viewed in natural order, represent a tensor of shape dimensions. See NTTShape for layout details. The transform is inplace, output adheres to shape.

The coset specifies the evaluation domain as an indexed coset of the subspace.

The transformation accepts a skip_rounds parameter, which is a number of NTT layers to skip at the end of the inverse transform. This corresponds to parallel NTTs on multiple adjacent subspace cosets, but returning with messages interpreted as coefficients in a modified novel polynomial basis. See DP24 Remark 4.15.

Provided Methods

fn forward_transform_ext<PE: PackedExtension<F>>( &self, data: &mut [PE], shape: NTTShape, coset: u32, skip_rounds: usize, ) -> Result<(), Error>

fn inverse_transform_ext<PE: PackedExtension<F>>( &self, data: &mut [PE], shape: NTTShape, coset: u32, skip_rounds: usize, ) -> Result<(), Error>

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<F, TA> AdditiveNTT<F> for MultithreadedNTT<F, TA>

where F: BinaryField, TA: TwiddleAccess<F> + Sync,

impl<F, TA> AdditiveNTT<F> for SingleThreadedNTT<F, TA>

where F: BinaryField, TA: TwiddleAccess<F>,

impl<F: BinaryField> AdditiveNTT<F> for DynamicDispatchNTT<F>