FLINT3.7.0-dev
/

_gr_poly_compose_mod, gr_poly_compose_mod, _gr_poly_compose_mod_horner, gr_poly_compose_mod_horner, _gr_poly_compose_mod_brent_kung, gr_poly_compose_mod_brent_kung, _gr_poly_compose_mod_preinv, gr_poly_compose_mod_preinv, _gr_poly_compose_mod_horner_preinv, gr_poly_compose_mod_horner_preinv, _gr_poly_compose_mod_brent_kung_preinv, gr_poly_compose_mod_brent_kung_preinv

Synopsis#include <flint/gr_poly.h>
int _gr_poly_compose_mod(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, gr_srcptr poly3, slong len3, gr_ctx_t ctx)source
int gr_poly_compose_mod(gr_poly_t res, const gr_poly_t poly1, const gr_poly_t poly2, const gr_poly_t poly3, gr_ctx_t ctx)source
int _gr_poly_compose_mod_horner(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, gr_srcptr poly3, slong len3, gr_ctx_t ctx)source
int gr_poly_compose_mod_horner(gr_poly_t res, const gr_poly_t poly1, const gr_poly_t poly2, const gr_poly_t poly3, gr_ctx_t ctx)source
int _gr_poly_compose_mod_brent_kung(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, gr_srcptr poly3, slong len3, gr_ctx_t ctx)source
int gr_poly_compose_mod_brent_kung(gr_poly_t res, const gr_poly_t poly1, const gr_poly_t poly2, const gr_poly_t poly3, gr_ctx_t ctx)source
int _gr_poly_compose_mod_preinv(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, gr_srcptr poly3, slong len3, gr_srcptr poly3inv, slong inv3len, gr_ctx_t ctx)source
int gr_poly_compose_mod_preinv(gr_poly_t res, const gr_poly_t poly1, const gr_poly_t poly2, const gr_poly_t poly3, const gr_poly_t poly3inv, gr_ctx_t ctx)source
int _gr_poly_compose_mod_horner_preinv(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, gr_srcptr poly3, slong len3, gr_srcptr poly3inv, slong inv3len, gr_ctx_t ctx)source
int gr_poly_compose_mod_horner_preinv(gr_poly_t res, const gr_poly_t poly1, const gr_poly_t poly2, const gr_poly_t poly3, const gr_poly_t poly3inv, gr_ctx_t ctx)source
int _gr_poly_compose_mod_brent_kung_preinv(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, gr_srcptr poly3, slong len3, gr_srcptr poly3inv, slong inv3len, gr_ctx_t ctx)source
int gr_poly_compose_mod_brent_kung_preinv(gr_poly_t res, const gr_poly_t poly1, const gr_poly_t poly2, const gr_poly_t poly3, const gr_poly_t poly3inv, gr_ctx_t ctx)source

Set res to f(g) mod hf(g) \bmod h, where ff, gg, hh are poly1, poly2, poly3, by Horner's rule (deg⁡h\deg h modular multiplications) or by the Brent-Kung baby-step giant-step algorithm [BrentKung1978], which computes m≈deg⁡hm \approx \sqrt{\deg h} powers of gg, multiplies a matrix of the coefficients of ff by the matrix of these powers, and combines the results by Horner's rule in gmg^m, so that the cost is dominated by one n×n\sqrt{n} \times n by n×nn \times \sqrt{n} matrix product. The preinv versions take the inverse poly3inv of the reversal of hh.

The default versions use Horner's rule when len3<6\mathit{len3} < 6 or len1≥len3\mathit{len1} \ge \mathit{len3} and Brent-Kung otherwise; the Brent-Kung versions themselves return GR_UNABLE when len1≥len3\mathit{len1} \ge \mathit{len3}, that is when ff is not reduced modulo hh. The non-underscore versions reduce gg modulo hh but not ff. The underscore functions require nonzero lengths and gg given with exactly len3−1\mathit{len3} - 1 coefficients (zero-padded), write len3−1\mathit{len3} - 1 coefficients, and do not allow aliasing.

References#

  • [BrentKung1978] Brent, R. P. and Kung, H. T. : Fast Algorithms for Manipulating Formal Power Series, J. ACM 25:4 (1978) 581–595
Cite this page

The FLINT team, “_gr_poly_compose_mod, gr_poly_compose_mod, _gr_poly_compose_mod_horner, gr_poly_compose_mod_horner, _gr_poly_compose_mod_brent_kung, gr_poly_compose_mod_brent_kung, _gr_poly_compose_mod_preinv, gr_poly_compose_mod_preinv, _gr_poly_compose_mod_horner_preinv, gr_poly_compose_mod_horner_preinv, _gr_poly_compose_mod_brent_kung_preinv, gr_poly_compose_mod_brent_kung_preinv (gr_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_poly/_gr_poly_compose_mod.html (generated 2026-11-02).