FLINT3.7.0-dev
/

_gr_poly_compose_mod_brent_kung_vec_preinv, gr_poly_compose_mod_brent_kung_vec_preinv

Synopsis#include <flint/gr_poly.h>
int _gr_poly_compose_mod_brent_kung_vec_preinv(gr_poly_struct * res, const gr_poly_struct * polys, slong lenpolys, slong l, gr_srcptr g, slong glen, gr_srcptr poly, slong len, gr_srcptr polyinv, slong leninv, gr_ctx_t ctx)source
int gr_poly_compose_mod_brent_kung_vec_preinv(gr_poly_struct * res, const gr_poly_struct * polys, slong len1, slong n, const gr_poly_t g, const gr_poly_t poly, const gr_poly_t polyinv, gr_ctx_t ctx)source

Set res[i] to polys[i] composed with gg modulo poly for 0≤i<n0 \le i < n (respectively ll), where polys holds len1 (respectively lenpolys) polynomials of degree less than that of poly and polyinv is the inverse of the reversal of poly. Compared with nn separate compositions, a single matrix product with splitting parameter m≈ndeg⁡(poly)m \approx \sqrt{n \deg(\mathit{poly})} reduces the number of modular multiplications by a factor n\sqrt{n}.

The underscore version requires gg of length at most len⁡(poly)−1\operatorname{len}(\mathit{poly}) - 1 and room for len⁡(poly)−1\operatorname{len}(\mathit{poly}) - 1 coefficients in each res[i]. The non-underscore version does not allow the output to be aliased with gg, poly or polyinv.

Cite this page

The FLINT team, “_gr_poly_compose_mod_brent_kung_vec_preinv, gr_poly_compose_mod_brent_kung_vec_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_brent_kung_vec_preinv.html (generated 2026-11-02).