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 a and b (Half-GCD): a 2 \times 2 matrix M of polynomials, a sign \sigma = \pm 1 = \det M and the consecutive remainders A, B with (A, B)^T = \sigma M^{-1} (a, b)^T and \deg A \ge \lceil \deg a / 2 \rceil > \deg B. The recursion uses the Euclidean algorithm below cutoff.

Requires \mathit{lena} > \mathit{lenb} > 0 and nonzero leading coefficients; returns GR_DOMAIN if a length is zero or a leading coefficient is not invertible. A and B must have room for \mathit{lena} and \mathit{lenb} coefficients; on return *lenA and *lenB hold their lengths. M[0], …, M[3] must each have room for \mathit{lena} coefficients, with the lengths written to lenM; if M is NULL, only A and B 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), as used by _gr_poly_resultant_hgcd. The input pairs (A, a) and (B, b) may be aliased.

The products of the 2 \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-10-20).