FLINT3.7.0-dev
/

_nmod_poly_compose_series, nmod_poly_compose_series

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

Set res to \mathit{poly1}(\mathit{poly2}) \bmod x^n, where poly2 must have constant term 0 (the non-underscore version throws FLINT_ERROR otherwise). The underscore version requires 0 < \mathit{len1}, \mathit{len2} \le n, writes n coefficients and does not allow aliasing.

The algorithm is chosen by _gr_poly_compose_series: Horner's rule for short inputs, a direct substitution for a monomial poly2, the divide-and-conquer algorithm when the composition is not much longer than n, the Brent–Kung baby-step giant-step algorithm [BrentKung1978] for n < 500, and the algorithm of Kinoshita and Li [KL2024], with O(M(n) \log n) operations, from n = 500 on.

References#

  • [BrentKung1978] Brent, R. P. and Kung, H. T. : Fast Algorithms for Manipulating Formal Power Series, J. ACM 25:4 (1978) 581–595
  • [KL2024] Y. Kinoshita and B. Li, "Power series composition in near-linear time", 2024, https://arxiv.org/abs/2404.05177
Cite this page

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