FLINT3.7.0-dev
/

_nmod_poly_divrem_newton_n_preinv, nmod_poly_divrem_newton_n_preinv

Synopsis#include <flint/nmod_poly.h>
void _nmod_poly_divrem_newton_n_preinv(nn_ptr Q, nn_ptr R, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nn_srcptr Binv, slong lenBinv, nmod_t mod)source
void nmod_poly_divrem_newton_n_preinv(nmod_poly_t Q, nmod_poly_t R, const nmod_poly_t A, const nmod_poly_t B, const nmod_poly_t Binv)source

Set QQ and RR to the quotient and remainder of AA by BB, given Binv as for nmod_poly_div_newton_n_preinv; the remainder is A−BQA - BQ computed by a short product. The underscore version requires lenA≥lenB≥1\mathit{lenA} \ge \mathit{lenB} \ge 1 and does not allow the outputs to overlap the inputs.

For quotients of length 2 the schoolbook routine is used with Binv[0] =lc⁡(B)−1= \operatorname{lc}(B)^{-1}. For lenB>20\mathit{lenB} > 20 and divisors with at most five nonzero coefficients below the leading one, the division is done directly in O(lenA)O(\mathit{lenA}) operations, which makes arithmetic modulo sparse polynomials, such as the trinomials and pentanomials used to define finite fields, efficient.

Guides#

Cite this page

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