FLINT3.7.0-dev
/

_fmpz_mod_poly_hgcd

Synopsis#include <flint/fmpz_mod_poly.h>
slong _fmpz_mod_poly_hgcd(fmpz ** M, slong * lenM, fmpz * A, slong * lenA, fmpz * B, slong * lenB, const fmpz * a, slong lena, const fmpz * b, slong lenb, const fmpz_mod_ctx_t ctx)source

One step of the half-GCD algorithm (_gr_poly_hgcd): for lena>lenb>0\mathit{lena} > \mathit{lenb} > 0, computes the 2×22 \times 2 matrix MM (the entries M[0], ..., M[3] with lengths lenM[0], ..., lenM[3], each with space for lena coefficients) and the two consecutive remainders AA, BB of the Euclidean remainder sequence of (a,b)(a, b) that straddle half the degree of aa, such that (A,B)T=σM−1(a,b)T(A, B)^T = \sigma M^{-1} (a, b)^T, and returns the sign σ=±1\sigma = \pm 1. AA and BB need space for lena and lenb coefficients; their lengths are returned in *lenA, *lenB. See Half-GCD.

Cite this page

The FLINT team, “_fmpz_mod_poly_hgcd (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_hgcd.html (generated 2026-11-02).