_nmod_poly_divrem_mpn_ctx
#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)sourceSets (q, a_n - b_n + 1) and (r, b_n - 1) to the quotient and remainder of (a, a_n) divided by (b, b_n) modulo n. Requires a_n \ge b_n \ge 2 and an invertible leading coefficient of b.
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 - bq computed modulo x^N - 1 with N the least power of two that is at least b_n - 1 and 256, which is exact because \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.
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-10-20).
@misc{flint-doc-fft-small-nmod-poly-divrem-mpn-ctx,
author = {{The FLINT team}},
title = {{\_nmod\_poly\_divrem\_mpn\_ctx (fft\_small.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/fft_small/_nmod_poly_divrem_mpn_ctx.html},
note = {Generated 2026-10-20}
}