FLINT3.7.0-dev
/

_nmod_poly_mullow_want_fft_small, _nmod_poly_mulmid_want_fft_small

Synopsis#include <flint/nmod_poly.h>
int _nmod_poly_mullow_want_fft_small(slong len1, slong len2, slong n, int squaring, nmod_t mod)source
int _nmod_poly_mulmid_want_fft_small(slong len2, slong m, nmod_t mod)source

Return whether fft_small is expected to be the fastest algorithm for a product of lengths len1 and len2 truncated to length nn (a full product if n=len1+len2−1n = \mathit{len1} + \mathit{len2} - 1), respectively for mm coefficients of a middle product whose shorter operand, after trimming, has length len2.

For full products the condition is min⁡(len1,2len2)\min(\mathit{len1}, 2 \mathit{len2}) at least a tabulated cutoff, one for each bit size of nn and separate ones for squaring, between about 80 and 1400. Moduli that are themselves one of the primes of the default fft_small context need no Chinese remaindering and use fft_small from min⁡(len1,2len2)≥24\min(\mathit{len1}, 2 \mathit{len2}) \ge 24. For n≤23n \le 23 (repacking) the full product length must exceed 370, with gaps just above the power-of-two lengths 512 and 1024 where the transform length doubles.

Cite this page

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