_fmpz_poly_mul_toom_scalar, _fmpz_poly_mul_toom_scalar_nmax, fmpz_poly_mul_toom_scalar
#include <flint/fmpz_poly.h>int _fmpz_poly_mul_toom_scalar(fmpz * res, const fmpz * poly1, slong len1, const fmpz * poly2, slong len2)sourceint _fmpz_poly_mul_toom_scalar_nmax(fmpz * res, const fmpz * poly1, slong len1, const fmpz * poly2, slong len2, slong nmax)sourceint fmpz_poly_mul_toom_scalar(fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2)sourceMultiply by Toom–Cook evaluation and interpolation in the polynomial variable, at the points 0, \pm 1, \ldots, \pm p, one more point when the output length is odd, and infinity, using exactly \mathit{len1} + \mathit{len2} - 1 coefficient multiplications. Return 1 on success and 0, leaving res unchanged, if the output length \mathit{len1} + \mathit{len2} - 1 exceeds FMPZ_POLY_TOOM_SCALAR_N_MAX (20 on 64-bit and 13 on 32-bit machines), respectively \min(\mathit{nmax}, FMPZ_POLY_TOOM_SCALAR_N_MAX).
The interpolation is table driven, runs in the output array without temporary allocation, and divides each row exactly by one word. The length bound is where the precomputed interpolation constants stop fitting in a word. Since the number of multiplications is minimal while the linear work grows quadratically with the length, the method pays off for short polynomials with large coefficients; the dispatcher uses it through _fmpz_poly_mul_toom_karatsuba, which caps the number of points according to the coefficient size.
The underscore versions require \mathit{len1} \ge \mathit{len2} > 0, allow zero padding and do not allow res to overlap the inputs. When poly1 and poly2 are the same array with the same length, the evaluations are shared and the pointwise products are squares. The non-underscore version allows aliasing.
The FLINT team, “_fmpz_poly_mul_toom_scalar, _fmpz_poly_mul_toom_scalar_nmax, fmpz_poly_mul_toom_scalar (fmpz_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpz_poly/_fmpz_poly_mul_toom_scalar.html (generated 2026-10-20).
@misc{flint-doc-fmpz-poly-fmpz-poly-mul-toom-scalar,
author = {{The FLINT team}},
title = {{\_fmpz\_poly\_mul\_toom\_scalar, \_fmpz\_poly\_mul\_toom\_scalar\_nmax, fmpz\_poly\_mul\_toom\_scalar (fmpz\_poly.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/fmpz_poly/_fmpz_poly_mul_toom_scalar.html},
note = {Generated 2026-10-20}
}