Struct FastPolyInterpolation

pub struct FastPolyInterpolation<P>
where
    P: RingStore,
    P::Type: PolyRing,
    <<P::Type as RingExtension>::BaseRing as RingStore>::Type: LinSolveRing,
{ /* private fields */ }

Interpolation data for a list of moduli f1, ..., fn that can be used to derive from remainders r1, ..., rn an “interpolation polynomial” h such that h = ri mod fi.

Clearly this requires that the moduli fi are pairwise coprime. Additionally, we currently require that all interpolation unit vectors ei (defined by ei = 1 mod fi, ei = 0 mod fj for j != i) exist over the base ring (e.g. they might not be integral, even if the base ring is Z).

Implementations

impl<P> FastPolyInterpolation<P>

where P: RingStore, P::Type: PolyRing, <<P::Type as RingExtension>::BaseRing as RingStore>::Type: LinSolveRing + FromModulusCreateableZnRing + ZnRing + PrincipalLocalRing, AsFieldBase<RingValue<<<P::Type as RingExtension>::BaseRing as RingStore>::Type>>: CanIsoFromTo<<<P::Type as RingExtension>::BaseRing as RingStore>::Type> + SelfIso,

pub fn new(poly_ring: P, moduli: Vec<El<P>>) -> Self

pub fn change_modulus<PNew>( &self, new_poly_ring: PNew, ) -> FastPolyInterpolation<PNew>

where PNew: RingStore, PNew::Type: PolyRing, <<PNew::Type as RingExtension>::BaseRing as RingStore>::Type: LinSolveRing + FromModulusCreateableZnRing + ZnRing + PrincipalLocalRing, AsFieldBase<RingValue<<<PNew::Type as RingExtension>::BaseRing as RingStore>::Type>>: CanIsoFromTo<<<PNew::Type as RingExtension>::BaseRing as RingStore>::Type> + SelfIso,

pub fn poly_ring(&self) -> &P

pub fn final_modulus(&self) -> &El<P>

pub fn interpolate_unreduced(&self, remainders: Vec<El<P>>) -> El<P>

Computes a polynomial of degree < 2 * deg(prod(moduli)) that is congruent to remainders[i] modulo moduli[i].

It is unreduced, since we can reduce its degree to < deg(prod(moduli)) by taking the remainder modulo prod(moduli).

However, this can be computed really fast, in time n log(n)^2 if FFT-based polynomial multiplication is used by the underlying polynomial ring. It is also very fast in practice, since we don’t perform any polynomial division.