Struct OddInterpolate

pub struct OddInterpolate<'a, F: BinaryField, NTT: AdditiveNTT<F>> { /* private fields */ }

A struct that can interpolate polynomials over odd NTT domains.

An odd NTT domain is an interpolation domain that is the union of multiple cosets of an additive subspace. The set of the domain is $d 2^{\ell}$. We generally care about the case when $d$ is an odd integer, otherwise $\ell$ could be incremented, though the struct handles even $d$ values as well (even though it’s suboptimal).

The complexity of the interpolation algorithm is $O(d^2 2^{\ell} + \ell 2^{\ell})$.

Implementations

impl<'a, F: BinaryField, NTT: AdditiveNTT<F>> OddInterpolate<'a, F, NTT>

pub fn new( ntt: &'a NTT, d: usize, ell: usize, coset_bits: usize, ) -> Result<Self, Error>

Create a new odd interpolator into novel polynomial basis for domains of size $d \times 2^{\ell}$. Takes a reference to NTT twiddle factors to seed the “Vandermonde” matrix and compute its inverse. Time complexity is $\mathcal{O}(d^3).$

pub fn inverse_transform(&self, data: &mut [F]) -> Result<(), Error>

Let $L/\mathbb F_2$ be a binary field, and fix an $\mathbb F_2$-basis $1=:\beta_0,\ldots, \beta_{r-1}$ as usual. Let $d\geq 1$ be an odd integer and let $\ell\geq 0$ be an integer. Let $[a_0,\ldots, a_{d\times 2^{\ell} - 1}]$ be a list of elements of $L$. There is a unique univariate polynomial $P(X)\in L[X]$ of degree less than $d\times 2^{\ell}$ such that the evaluations of $P$ on the “first” $d\times 2^{\ell}$ elements of $L$ (in little-Endian binary counting order with respect to the basis $\beta_0,\ldots, \beta_{r}$) are precisely $a_0,\ldots, a_{d\times 2^{\ell} - 1}$.

We efficiently compute the coefficients of $P(X)$ with respect to the Novel Polynomial Basis (itself taken with respect to the given ordered list $\beta_0,\ldots, \beta_{r-1}$).

Time complexity is $\mathcal{O}(d^2\times 2^{\ell} + \ell 2^{\ell})$, thus this routine is intended to be used for small values of $d$.

Trait Implementations

impl<'a, F: Debug + BinaryField, NTT: Debug + AdditiveNTT<F>> Debug for OddInterpolate<'a, F, NTT>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.