FLINT3.7.0-dev
/

_nmod_poly_mul_KS2, nmod_poly_mul_KS2

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

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

Write f(x) = f_e(x^2) + x f_o(x^2) for even and odd parts. The two integer products h(2^b) and h(-2^b) of length about half that of _nmod_poly_mul_KS give 2 h_e(2^{2b}) = h(2^b) + h(-2^b) and 2^{b+1} h_o(2^{2b}) = h(2^b) - h(-2^b), from which the even and odd coefficients of the product are unpacked separately with _nmod_poly_KS2_unpack and reduced with _nmod_poly_KS2_reduce.

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_KS2, nmod_poly_mul_KS2 (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_KS2.html (generated 2026-10-20).