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 \mathit{lenR} \le 2d (any length for _fq_sparse_reduce), modulo p and modulo the defining polynomial f in place: the first \min(\mathit{lenR}, d) coefficients receive the reduced value (and are not normalised). _fq_sparse_reduce eliminates the coefficients of degree at least d from the top, using the nonzero terms of the monic version of f, and reduces modulo p at the end; it costs about (\mathit{lenR} - d) \cdot t multiplications for f with t nonzero terms. _fq_dense_reduce reduces modulo p and then divides by f with the precomputed inverse (Newton division, _fmpz_mod_poly_divrem_newton_n_preinv). _fq_reduce calls the first if f 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-10-20).