_fmpz_mod_poly_xgcd, fmpz_mod_poly_xgcd
#include <flint/fmpz_mod_poly.h>slong _fmpz_mod_poly_xgcd(fmpz * G, fmpz * S, fmpz * T, const fmpz * A, slong lenA, const fmpz * B, slong lenB, const fmpz_t invB, const fmpz_mod_ctx_t ctx)sourcevoid fmpz_mod_poly_xgcd(fmpz_mod_poly_t G, fmpz_mod_poly_t S, fmpz_mod_poly_t T, const fmpz_mod_poly_t A, const fmpz_mod_poly_t B, const fmpz_mod_ctx_t ctx)sourceCompute the GCD G of A and B and cofactors with SA + TB = G. The non-underscore version makes G monic, with \deg S < \deg B and \deg T < \deg A (if A or B is nonzero; if both are zero, all outputs are zero). The underscore version requires \mathit{lenA} \ge \mathit{lenB} \ge 1 with (\mathit{lenA}, \mathit{lenB}) \ne (1, 1), does not make G monic, needs space for \mathit{lenB}, \mathit{lenB} - 1 and \mathit{lenA} - 1 coefficients in G, S, T, returns the length of G, and does not allow aliasing (invB is not used). The modulus must be prime.
The Euclidean algorithm is used for \min(\mathit{lenA}, \mathit{lenB}) < 256, and the half-GCD algorithm above that (_gr_poly_xgcd_euclidean, _gr_poly_xgcd_hgcd).
The FLINT team, “_fmpz_mod_poly_xgcd, fmpz_mod_poly_xgcd (fmpz_mod_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpz_mod_poly/_fmpz_mod_poly_xgcd.html (generated 2026-10-20).
@misc{flint-doc-fmpz-mod-poly-fmpz-mod-poly-xgcd,
author = {{The FLINT team}},
title = {{\_fmpz\_mod\_poly\_xgcd, fmpz\_mod\_poly\_xgcd (fmpz\_mod\_poly.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/fmpz_mod_poly/_fmpz_mod_poly_xgcd.html},
note = {Generated 2026-10-20}
}