FLINT3.7.0-dev
/

_nmod_poly_interpolate_geometric_nmod_vec_fast_precomp, nmod_poly_interpolate_geometric_nmod_vec_fast_precomp

Synopsis#include <flint/nmod_poly.h>
void _nmod_poly_interpolate_geometric_nmod_vec_fast_precomp(nn_ptr poly, nn_srcptr v, const nmod_geometric_progression_t G, slong len, nmod_t mod)source
void nmod_poly_interpolate_geometric_nmod_vec_fast_precomp(nmod_poly_t poly, nn_srcptr v, const nmod_geometric_progression_t G, slong len)source

Set poly to the polynomial of length at most len taking the values v[i] at r^{2i}, 0 \le i < \mathit{len}, using G prepared for interpolation. Requires 1 \le \mathit{len} \le G->len. The underscore version writes len coefficients and does not allow poly to overlap v.

Following [BS2005, §5], the values are first converted to the Newton basis of the progression by one short product and then to the monomial basis by a transposed short product, with scalings by the precomputed \prod_{k \le i} (q^k - 1) and q^{i(i-1)/2}.

References#

  • [BS2005] A. Bostan and É. Schost. Polynomial evaluation and interpolation on special sets of points. Journal of Complexity 21 (2005), 420–446.
Cite this page

The FLINT team, “_nmod_poly_interpolate_geometric_nmod_vec_fast_precomp, nmod_poly_interpolate_geometric_nmod_vec_fast_precomp (nmod_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nmod_poly/_nmod_poly_interpolate_geometric_nmod_vec_fast_precomp.html (generated 2026-10-20).