binius_ntt/
additive_ntt.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3use binius_field::{BinaryField, ExtensionField, PackedExtension, PackedField};
4use binius_math::BinarySubspace;
5
6use super::error::Error;
7
8/// The binary field additive NTT.
9///
10/// A number-theoretic transform (NTT) is a linear transformation on a finite field analogous to
11/// the discrete fourier transform. The version of the additive NTT we use is originally described
12/// in [LCH14]. In [DP24] Section 3.1, the authors present the LCH additive NTT algorithm in a way
13/// that makes apparent its compatibility with the FRI proximity test. Throughout the
14/// documentation, we will refer to the notation used in [DP24].
15///
16/// The additive NTT is parameterized by a binary field $K$ and $\mathbb{F}_2$-linear subspace. We
17/// write $\beta_0, \ldots, \beta_{\ell-1}$ for the ordered basis elements of the subspace and
18/// require $\beta_0 = 1$. The basis determines a novel polynomial basis and an evaluation domain.
19/// In the forward direction, the additive NTT transforms a vector of polynomial coefficients, with
20/// respect to the novel polynomial basis, into a vector of their evaluations over the evaluation
21/// domain. The inverse transformation interpolates polynomial values over the domain into novel
22/// polynomial basis coefficients.
23///
24/// [LCH14]: <https://arxiv.org/abs/1404.3458>
25/// [DP24]: <https://eprint.iacr.org/2024/504>
26pub trait AdditiveNTT<F: BinaryField> {
27	/// Base-2 logarithm of the maximum size of the NTT domain, $\ell$.
28	fn log_domain_size(&self) -> usize;
29
30	/// Returns the binary subspace $S^(i)$.
31	///
32	/// The domain will have dimension $\ell - i$.
33	///
34	/// ## Preconditions
35	///
36	/// * `i` must be less than `self.log_domain_size()`
37	fn subspace(&self, i: usize) -> BinarySubspace<F>;
38
39	/// Get the normalized subspace polynomial evaluation $\hat{W}_i(\beta_j)$.
40	///
41	/// ## Preconditions
42	///
43	/// * `i` must be less than `self.log_domain_size()`
44	/// * `j` must be less than `self.log_domain_size() - i`
45	fn get_subspace_eval(&self, i: usize, j: usize) -> F;
46
47	/// Forward transformation defined in [LCH14] on a batch of inputs.
48	///
49	/// Input is the vector of polynomial coefficients in novel basis, output is in Lagrange basis.
50	/// The batched inputs are interleaved, which improves the cache-efficiency of the computation.
51	///
52	/// [LCH14]: <https://arxiv.org/abs/1404.3458>
53	fn forward_transform<P: PackedField<Scalar = F>>(
54		&self,
55		data: &mut [P],
56		coset: u32,
57		log_batch_size: usize,
58		log_n: usize,
59	) -> Result<(), Error>;
60
61	/// Inverse transformation defined in [LCH14] on a batch of inputs.
62	///
63	/// Input is the vector of polynomial coefficients in Lagrange basis, output is in novel basis.
64	/// The batched inputs are interleaved, which improves the cache-efficiency of the computation.
65	///
66	/// [LCH14]: https://arxiv.org/abs/1404.3458
67	fn inverse_transform<P: PackedField<Scalar = F>>(
68		&self,
69		data: &mut [P],
70		coset: u32,
71		log_batch_size: usize,
72		log_n: usize,
73	) -> Result<(), Error>;
74
75	fn forward_transform_ext<PE: PackedExtension<F>>(
76		&self,
77		data: &mut [PE],
78		coset: u32,
79		log_n: usize,
80	) -> Result<(), Error> {
81		self.forward_transform(PE::cast_bases_mut(data), coset, PE::Scalar::LOG_DEGREE, log_n)
82	}
83
84	fn inverse_transform_ext<PE: PackedExtension<F>>(
85		&self,
86		data: &mut [PE],
87		coset: u32,
88		log_n: usize,
89	) -> Result<(), Error> {
90		self.inverse_transform(PE::cast_bases_mut(data), coset, PE::Scalar::LOG_DEGREE, log_n)
91	}
92}
binius_ntt/additive_ntt.rs

binius_ntt/
additive_ntt.rs
