FLINT3.7.0-dev

_fq_reduce, _fq_sparse_reduce, _fq_dense_reduce

Synopsis#include <flint/fq.h>
void _fq_reduce(fmpz * R, slong lenR, const fq_ctx_t ctx)source
void _fq_sparse_reduce(fmpz * R, slong lenR, const fq_ctx_t ctx)source
void _fq_dense_reduce(fmpz * R, slong lenR, const fq_ctx_t ctx)source

Reduce the polynomial (R, lenR), with arbitrary integer coefficients and lenR≤2d\mathit{lenR} \le 2d (any length for _fq_sparse_reduce), modulo pp and modulo the defining polynomial ff in place: the first min⁡(lenR,d)\min(\mathit{lenR}, d) coefficients receive the reduced value (and are not normalised). _fq_sparse_reduce eliminates the coefficients of degree at least dd from the top, using the nonzero terms of the monic version of ff, and reduces modulo pp at the end; it costs about (lenR−d)⋅t(\mathit{lenR} - d) \cdot t multiplications for ff with tt nonzero terms. _fq_dense_reduce reduces modulo pp and then divides by ff with the precomputed inverse (Newton division, _fmpz_mod_poly_divrem_newton_n_preinv). _fq_reduce calls the first if ff has at most five nonzero terms and the second otherwise.

Cite this page

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