_mpn_mod_poly_gcd, _mpn_mod_poly_xgcd
#include <flint/mpn_mod.h>int _mpn_mod_poly_gcd(nn_ptr G, slong * lenG, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, gr_ctx_t ctx)sourceint _mpn_mod_poly_xgcd(slong * lenG, nn_ptr G, nn_ptr S, nn_ptr T, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, gr_ctx_t ctx)sourceGreatest common divisor and extended gcd, with the conventions of _gr_poly_gcd and _gr_poly_xgcd. They use the Euclidean algorithm (_gr_poly_gcd_euclidean, _gr_poly_xgcd_euclidean), whose division steps are _mpn_mod_poly_divrem_q1_preinv1, if either length is below 240, and the half-gcd algorithm (_gr_poly_gcd_hgcd, _gr_poly_xgcd_hgcd with inner cutoff 80 and outer cutoff 240) otherwise; see Half-GCD. The modulus should be prime, or the ring should pretend to be a field: a non-invertible leading coefficient gives GR_DOMAIN (GR_UNABLE when pretending, recording a factor of n).
The FLINT team, “_mpn_mod_poly_gcd, _mpn_mod_poly_xgcd (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_gcd.html (generated 2026-10-20).
@misc{flint-doc-mpn-mod-mpn-mod-poly-gcd,
author = {{The FLINT team}},
title = {{\_mpn\_mod\_poly\_gcd, \_mpn\_mod\_poly\_xgcd (mpn\_mod.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/mpn_mod/_mpn_mod_poly_gcd.html},
note = {Generated 2026-10-20}
}