FLINT3.7.0-dev
/

_mpn_mod_poly_divrem_basecase, _mpn_mod_poly_divrem_basecase_preinv1

Synopsis#include <flint/mpn_mod.h>
int _mpn_mod_poly_divrem_basecase(nn_ptr Q, nn_ptr R, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, gr_ctx_t ctx)source
int _mpn_mod_poly_divrem_basecase_preinv1(nn_ptr Q, nn_ptr R, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nn_srcptr invL, gr_ctx_t ctx)source

Schoolbook division with remainder. The preinv1 version takes the inverse invL of the leading coefficient of B; the other computes it and returns GR_DOMAIN (or GR_UNABLE) if it does not exist.

The partial remainder is kept unreduced in \lceil (2b + \lfloor \log_2 (\mathit{lenA} - \mathit{lenB} + 1) \rfloor + 1) / \mathtt{FLINT\_BITS} \rceil limbs per coefficient, so that each quotient coefficient costs \mathit{lenB} - 1 plain multiplications and additions and one reduction (Division with remainder). The cases \mathit{lenB} = 1, \mathit{lenA} = \mathit{lenB} and \mathit{lenA} = \mathit{lenB} + 1 (the step of Euclid's algorithm) have special code; a monic divisor saves the multiplications by invL.

Cite this page

The FLINT team, “_mpn_mod_poly_divrem_basecase, _mpn_mod_poly_divrem_basecase_preinv1 (mpn_mod.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mpn_mod/_mpn_mod_poly_divrem_basecase.html (generated 2026-10-20).