FLINT3.7.0-dev

_nmod_poly_mul_classical, nmod_poly_mul_classical

Synopsis#include <flint/nmod_poly.h>
void _nmod_poly_mul_classical(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, nmod_t mod)source
void nmod_poly_mul_classical(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2)source

Set res to the product by the classical algorithm, with O(len1⋅len2)O(\mathit{len1} \cdot \mathit{len2}) operations. The underscore version requires len1,len2≥1\mathit{len1}, \mathit{len2} \ge 1, in either order, and does not allow aliasing.

If (n−1)2min⁡(len1,len2)(n-1)^2 \min(\mathit{len1}, \mathit{len2}) fits in one word, the products are accumulated without reduction, one pass over the longer operand for each coefficient of the shorter one, and every coefficient is reduced once at the end. Otherwise each coefficient is a dot product computed with _nmod_vec_dot_rev, whose method is chosen once for the longest dot product. Squaring uses the symmetry of the product and does about half the multiplications.

Cite this page

The FLINT team, “_nmod_poly_mul_classical, nmod_poly_mul_classical (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_classical.html (generated 2026-11-20).