FLINT3.7.0-dev
/

_fmpz_mod_poly_xgcd, fmpz_mod_poly_xgcd

Synopsis#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)source
void 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)source

Compute the GCD GG of AA and BB and cofactors with SA+TB=GSA + TB = G. The non-underscore version makes GG monic, with deg⁡S<deg⁡B\deg S < \deg B and deg⁡T<deg⁡A\deg T < \deg A (if AA or BB is nonzero; if both are zero, all outputs are zero). The underscore version requires lenA≥lenB≥1\mathit{lenA} \ge \mathit{lenB} \ge 1 with (lenA,lenB)≠(1,1)(\mathit{lenA}, \mathit{lenB}) \ne (1, 1), does not make GG monic, needs space for lenB\mathit{lenB}, lenB−1\mathit{lenB} - 1 and lenA−1\mathit{lenA} - 1 coefficients in GG, SS, TT, returns the length of GG, and does not allow aliasing (invB is not used). The modulus must be prime.

The Euclidean algorithm is used for min⁡(lenA,lenB)<256\min(\mathit{lenA}, \mathit{lenB}) < 256, and the half-GCD algorithm above that (_gr_poly_xgcd_euclidean, _gr_poly_xgcd_hgcd).

Cite this page

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-11-02).