Trait binius_ntt::twiddle::TwiddleAccess
source · pub trait TwiddleAccess<F: BinaryField> {
// Required methods
fn log_n(&self) -> usize;
fn get(&self, index: usize) -> F;
fn get_pair(&self, index_bits: usize, index: usize) -> (F, F);
fn coset(&self, coset_bits: usize, coset: usize) -> impl TwiddleAccess<F>;
}Expand description
A trait for accessing twiddle factors in a single NTT round.
Twiddle factors in the additive NTT are subspace polynomial evaluations over linear subspaces, with an implicit NTT round $i$. Setup: let $K/\mathbb{F}_2$ be a finite extension of degree $d$, and let $\beta_0,\ldots ,\beta_{d-1}$ be a linear basis. Let $U_i$ be the $\mathbb{F}_2$-linear span of $\beta_0,\ldots ,\beta_{i-1}$. Let $\hat{W}_i(X)$ be the normalized subspace polynomial of degree $2^i$ that vanishes on $U_i$ and is $1$ on $\beta_i$. Evaluating $\hat{W}_i(X)$ turns out to yield an $\mathbb{F}_2$-linear function $K\rightarrow K$.
This trait accesses the subspace polynomial evaluations for $\hat{W}_i(X)$. The evaluations of the vanishing polynomial over all elements in any coset of the subspace are equal. Equivalently, the evaluations of $\hat{W}_i(X)$ are well-defined on the $d-i$-dimensional vector space $K/U_{i-1}$. Note that $K/U_{i-1}$ has a natural induced basis. Write ${j}$ for the $j$th coset of the subspace, where $j$ is in $[0,2^{d-i})$, with respect to this natural basis. This means: write $j$ in binary: $j = j_0 + \ldots +j_{d-i-1}2^{d-i-1}$ and consider the following element of $K$: $j_0\beta_i + \ldots + j_{d-i-1}\beta_{d-1}$. This element of course specifies an element of $K/U_i$. The twiddle factor $t_{i,j}$ is then $\hat{W}_i({j})$, i.e., $\hat{W}_j$ evaluated at the aforementioned element of the quotient $K/U_i$.
As explained, the evaluations of these polynomial yield linear functions, which allows for flexibility in how they are computed.
Namely, for an evaluation domain of size $2^{i}$, there is a strategy for computing polynomial
evaluations “on-the-fly” with $O(\ell)$ field additions using $O(\ell)$ stored elements or precomputing the $2^\ell$ evaluations and
looking them up in constant time (see the OnTheFlyTwiddleAccess and
PrecomputedTwiddleAccess implementations, respectively).
Required Methods§
sourcefn get(&self, index: usize) -> F
fn get(&self, index: usize) -> F
Get the twiddle factor at the given index.
Evaluate $\hat{W}_i(X)$ at the element index: write index in binary
and evaluate at the element $index_0\beta_{i+1} \ldots + index_{d-i-2}\beta_{d-1}$.
Panics if index is not in the range 0 to 1 << self.log_n().
sourcefn get_pair(&self, index_bits: usize, index: usize) -> (F, F)
fn get_pair(&self, index_bits: usize, index: usize) -> (F, F)
Get the pair of twiddle factors at the indices index and (1 << index_bits) | index.
Panics if index_bits is not in the range 0 to self.log_n() or index is not in the
range 0 to 1 << index_bits.
sourcefn coset(&self, coset_bits: usize, coset: usize) -> impl TwiddleAccess<F>
fn coset(&self, coset_bits: usize, coset: usize) -> impl TwiddleAccess<F>
Returns a scoped twiddle access for the coset that fixes the upper coset_bits of the
index to coset.
Recall that a TwiddleAccess has an implicit NTT round $i$. Let $j=d-coset_{bits}$.
Thencoset returns a TwiddleAccess object (of NTT round i) for the following affine
subspace of $K/U_{i-1}$: the set of all elements of $K/U_{i-1}$
whose coordinates in the basis $\beta_i,\ldots ,\beta_{d-1}$ is:
$(*, \cdots, *, coset_{0}, \ldots , coset_{bits-1})$, where the first $j$ coordinates are arbitrary.
Here $coset = coset_0 + \ldots + coset_{bits-1}2^{bits-1}$. In sum, this amounts to evaluations of $\hat{W}_i$
at all such elements.
Therefore, the self.log_n of the new TwiddleAccess object is computed as self.log_n() - coset_bits.
Panics if coset_bits is not in the range 0 to self.log_n() or coset is not in the
range 0 to 1 << coset_bits.