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) \bmod h, where f, g, h are poly1, poly2, poly3, by Horner's rule (\deg h modular multiplications) or by the Brent-Kung baby-step giant-step algorithm [BrentKung1978], which computes m \approx \sqrt{\deg h} powers of g, multiplies a matrix of the coefficients of f by the matrix of these powers, and combines the results by Horner's rule in g^m, so that the cost is dominated by one \sqrt{n} \times n by n \times \sqrt{n} matrix product. The preinv versions take the inverse poly3inv of the reversal of h.

The default versions use Horner's rule when \mathit{len3} < 6 or \mathit{len1} \ge \mathit{len3} and Brent-Kung otherwise; the Brent-Kung versions themselves return GR_UNABLE when \mathit{len1} \ge \mathit{len3}, that is when f is not reduced modulo h. The non-underscore versions reduce g modulo h but not f. The underscore functions require nonzero lengths and g given with exactly \mathit{len3} - 1 coefficients (zero-padded), write \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-10-20).