fmpz_mpolyl_gcd_brown, fmpz_mpolyl_gcd_brown_threaded_pool
#include <flint/fmpz_mpoly_factor.h>int fmpz_mpolyl_gcd_brown(fmpz_mpoly_t G, fmpz_mpoly_t Abar, fmpz_mpoly_t Bbar, fmpz_mpoly_t A, fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx, const mpoly_gcd_info_t Iv)sourceint fmpz_mpolyl_gcd_brown_threaded_pool(fmpz_mpoly_t G, fmpz_mpoly_t Abar, fmpz_mpoly_t Bbar, fmpz_mpoly_t A, fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx, const mpoly_gcd_info_t Iv, const thread_pool_handle * handles, slong num_handles)sourceBrown's dense multimodular algorithm [Bro1971] for the GCD and cofactors of nonzero and . The integer contents are removed from and , which are modified. Images are computed with nmod_mpolyn_gcd_brown_smprime modulo primes not dividing the GCD of the leading coefficients, scaled to have leading coefficient and combined by Chinese remaindering, discarding images of too large degree. The loop stops when the product of the primes exceeds twice times the larger height of and and the reconstructed , , satisfy and likewise for ; this proves and without a division. Iv (possibly NULL) supplies degree bounds for the images. The threaded version computes images for different primes in parallel using the given thread pool handles; it is not used by fmpz_mpoly_gcd. Return 0 if the primes run out.
References#
- [Bro1971] W. S. Brown. On Euclid's algorithm and the computation of polynomial greatest common divisors. Journal of the ACM 18:4 (1971), 478–504. https://doi.org/10.1145/321662.321664
The FLINT team, “fmpz_mpolyl_gcd_brown, fmpz_mpolyl_gcd_brown_threaded_pool (fmpz_mpoly_factor.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpz_mpoly_factor/fmpz_mpolyl_gcd_brown.html (generated 2026-11-02).
@misc{flint-doc-fmpz-mpoly-factor-fmpz-mpolyl-gcd-brown,
author = {{The FLINT team}},
title = {{fmpz\_mpolyl\_gcd\_brown, fmpz\_mpolyl\_gcd\_brown\_threaded\_pool (fmpz\_mpoly\_factor.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/fmpz_mpoly_factor/fmpz_mpolyl_gcd_brown.html},
note = {Generated 2026-11-02}
}