Struct OddInterpolate

pub struct OddInterpolate<F: BinaryField> { /* private fields */ }

Implementations

impl<F: BinaryField> OddInterpolate<F>

pub fn new<TA>( d: usize, ell: usize, twiddle_access: &[TA], ) -> Result<Self, Error>

where TA: TwiddleAccess<F>,

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<NTT>( &self, ntt: &NTT, data: &mut [F], ) -> Result<(), Error>

where NTT: AdditiveNTT<F>,

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