FLINT3.7.0-dev

fmpz_mpolyl_gcd_brown, fmpz_mpolyl_gcd_brown_threaded_pool

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

Brown's dense multimodular algorithm [Bro1971] for the GCD and cofactors of nonzero A and B. The integer contents are removed from A and B, which are modified. Images are computed with nmod_mpolyn_gcd_brown_smprime modulo primes p > 2^{\mathrm{FLINT\_BITS}-1} not dividing the GCD \gamma of the leading coefficients, scaled to have leading coefficient \gamma \bmod p and combined by Chinese remaindering, discarding images of too large degree. The loop stops when the product m of the primes exceeds twice \gamma times the larger height of A and B and the reconstructed H, \bar A_H, \bar B_H satisfy 2 \min(\|H\|_\infty \|\bar A_H\|_1, \|H\|_1 \|\bar A_H\|_\infty) < m and likewise for B; this proves H \bar A_H = \gamma A and H \bar B_H = \gamma B 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
Cite this page

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-10-20).