FLINT3.7.0-dev
/

_gr_poly_hgcd

Synopsis#include <flint/gr_poly.h>
int _gr_poly_hgcd(gr_ptr r, slong * sgn, gr_ptr * M, slong * lenM, gr_ptr A, slong * lenA, gr_ptr B, slong * lenB, gr_srcptr a, slong lena, gr_srcptr b, slong lenb, slong cutoff, gr_ctx_t ctx)source

Computes the half-gcd of aa and bb (Half-GCD): a 2×22 \times 2 matrix MM of polynomials, a sign σ=±1=det⁡M\sigma = \pm 1 = \det M and the consecutive remainders AA, BB with (A,B)T=σM−1(a,b)T(A, B)^T = \sigma M^{-1} (a, b)^T and deg⁡A≥⌈deg⁡a/2⌉>deg⁡B\deg A \ge \lceil \deg a / 2 \rceil > \deg B. The recursion uses the Euclidean algorithm below cutoff.

Requires lena>lenb>0\mathit{lena} > \mathit{lenb} > 0 and nonzero leading coefficients; returns GR_DOMAIN if a length is zero or a leading coefficient is not invertible. AA and BB must have room for lena\mathit{lena} and lenb\mathit{lenb} coefficients; on return *lenA and *lenB hold their lengths. M[0], …, M[3] must each have room for lena\mathit{lena} coefficients, with the lengths written to lenM; if M is NULL, only AA and BB are computed. If r is not NULL, it is an accumulator for the resultant: it is multiplied by the factor contributed by the remainder sequence up to (A,B)(A, B), as used by _gr_poly_resultant_hgcd. The input pairs (A, a) and (B, b) may be aliased.

The products of the 2×22 \times 2 polynomial matrices are done by _gr_poly_hgcd_mat_mul, a ring method; the default _gr_poly_hgcd_mat_mul_generic uses 8 classical products when some entry has length below 20 and Strassen's 7 products otherwise, and when the ring provides a transformed representation (with fft_small) and all entries have length at least 128, it transforms each of the 8 entries once and computes the products pointwise, in several threads for entries of length at least 1024.

Cite this page

The FLINT team, “_gr_poly_hgcd (gr_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_poly/_gr_poly_hgcd.html (generated 2026-11-02).