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 AA and BB. The integer contents are removed from AA and BB, which are modified. Images are computed with nmod_mpolyn_gcd_brown_smprime modulo primes p>2FLINT_BITS−1p > 2^{\mathrm{FLINT\_BITS}-1} not dividing the GCD γ\gamma of the leading coefficients, scaled to have leading coefficient γ mod p\gamma \bmod p and combined by Chinese remaindering, discarding images of too large degree. The loop stops when the product mm of the primes exceeds twice γ\gamma times the larger height of AA and BB and the reconstructed HH, AˉH\bar A_H, BˉH\bar B_H satisfy 2min⁡(∥H∥∞∥AˉH∥1,∥H∥1∥AˉH∥∞)<m2 \min(\|H\|_\infty \|\bar A_H\|_1, \|H\|_1 \|\bar A_H\|_\infty) < m and likewise for BB; this proves HAˉH=γAH \bar A_H = \gamma A and HBˉH=γBH \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-11-02).