FLINT3.7.0-dev
/

_nmod_poly_mul_KS4, nmod_poly_mul_KS4

Synopsis#include <flint/nmod_poly.h>
void _nmod_poly_mul_KS4(nn_ptr res, nn_srcptr op1, slong n1, nn_srcptr op2, slong n2, nmod_t mod)source
void nmod_poly_mul_KS4(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2)source

Set res to the product by Kronecker substitution at ±2b\pm 2^b and at the reciprocal points ±2−b\pm 2^{-b} [Har2009a]. The underscore version requires n1≥n2≥1\mathit{n1} \ge \mathit{n2} \ge 1.

The evaluations at ±2−b\pm 2^{-b} are evaluations of the reversed polynomials. They give the high halves of the coefficients of the product, the evaluations at ±2b\pm 2^b the low halves, so each of the four integer products needs fields of only about half the width; _nmod_poly_KS2_recover_reduce combines the two halves and reduces them.

References#

  • [Har2009a] D. Harvey, "Faster polynomial multiplication via multipoint Kronecker substitution", Journal of Symbolic Computation 44:10 (2009), 1502–1510
Cite this page

The FLINT team, “_nmod_poly_mul_KS4, nmod_poly_mul_KS4 (nmod_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nmod_poly/_nmod_poly_mul_KS4.html (generated 2026-11-02).