FLINT3.7.0-dev
/

_nmod_poly_divrem_mpn_ctx

Synopsis#include <flint/fft_small.h>
void _nmod_poly_divrem_mpn_ctx(ulong * q, ulong * r, const ulong * a, ulong an, const ulong * b, ulong bn, nmod_t mod, mpn_ctx_t R)source

Sets (q,an−bn+1)(q, a_n - b_n + 1) and (r,bn−1)(r, b_n - 1) to the quotient and remainder of (a,an)(a, a_n) divided by (b,bn)(b, b_n) modulo nn. Requires an≥bn≥2a_n \ge b_n \ge 2 and an invertible leading coefficient of bb.

The quotient is a middle product of the reversed dividend with a power series inverse of the reversed divisor, computed by _nmod_poly_inv_series; the remainder is a−bqa - bq computed modulo xN−1x^N - 1 with NN the least power of two that is at least bn−1b_n - 1 and 256, which is exact because deg⁡r<bn−1≤N\deg r < b_n - 1 \le N. FLINT's nmod_poly_divrem does not call this function; see Products and divisions with a fixed operand for the version with a precomputed divisor.

Cite this page

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