`_nmod_poly_mulmid_fft_small_repack`

Synopsis#include <flint/nmod_poly.h>

int _nmod_poly_mulmid_fft_small_repack(nn_ptr z, nn_srcptr a, slong an, nn_srcptr b, slong bn, slong znlo, slong zn, nmod_t mod)

source

Internal helper of _nmod_poly_mulmid_fft_small for $n \le 23$ : if the coefficients are small enough, writes the coefficients $\mathit{znlo}, \ldots, \mathit{zn} - 1$ of the product to z and returns 1; otherwise returns 0 without writing anything. The conditions on the arguments are those of _nmod_poly_mulmid_fft_small.

With $A_2(x) = \sum_k (a_{2k} + a_{2k+1} M) x^k$ and $B_2$ likewise, for $M = 2^{16}$ or $2^{17}$ , the product $A_2 B_2$ computed modulo the prime $p = 1108307720798209$ has coefficients $c_0 + c_1 M + c_2 M^2$ from which the coefficients of $AB$ are read off, provided that $c_0, c_1 < M$ and $c_2 M^2 < p$ . These conditions are checked with the bound $\min(\mathit{an}, \mathit{bn}) (n-1)^2$ or, if that fails, with the Cauchy–Schwarz inequality applied to the even and odd parts.

Cite this page

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

@misc{flint-doc-nmod-poly-nmod-poly-mulmid-fft-small-repack,
  author       = {{The FLINT team}},
  title        = {{\_nmod\_poly\_mulmid\_fft\_small\_repack (nmod\_poly.h)}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/nmod_poly/_nmod_poly_mulmid_fft_small_repack.html},
  note         = {Generated 2026-11-02}
}

Edit this page · PDF version · Built with fdoc from 0a4634bf95