Trait AdditiveNTT

Source

pub trait AdditiveNTT {
    type Field: BinaryField;

    // Required methods
    fn forward_transform<P: PackedField<Scalar = Self::Field>>(
        &self,
        data: FieldSliceMut<'_, P>,
        skip_early: usize,
        skip_late: usize,
    );
    fn inverse_transform<P: PackedField<Scalar = Self::Field>>(
        &self,
        data: FieldSliceMut<'_, P>,
        skip_early: usize,
        skip_late: usize,
    );
    fn domain_context(&self) -> &impl DomainContext<Field = Self::Field>;

    // Provided methods
    fn log_domain_size(&self) -> usize { ... }
    fn subspace(&self, i: usize) -> BinarySubspace<Self::Field> { ... }
    fn twiddle(&self, i: usize, j: usize) -> Self::Field { ... }
}

Expand description

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 4.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. 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.

An AdditiveNTT implementation with a maximum domain dimension of $\ell$ can be applied on a sequence of $\ell + 1$ evaluation domains of sizes $2^0, \ldots, 2^\ell$. These are the domains $S^{(\ell)}, S^{(\ell - 1)}, \ldots, S^{(0)}$ defined in DP24 Section 4. The methods Self::forward_transform and Self::inverse_transform require a parameter log_domain_size that indicates which of the $S^(i)$ domains to use for the transformation’s evaluation domain and novel polynomial basis. (Remember, the novel polynomial basis is itself parameterized by basis). Counterintuitively, the space $S^(i+1)$ is not necessarily a subset of $S^i$. We choose this behavior for the AdditiveNTT trait because it facilitates compatibility with FRI when batching proximity tests for codewords of different dimensions.