fmpz_mpolyl_gcd_zippel
Synopsis
#include <flint/fmpz_mpoly_factor.h>int fmpz_mpolyl_gcd_zippel(fmpz_mpoly_t G, fmpz_mpoly_t Abar, fmpz_mpoly_t Bbar, const fmpz_mpoly_t A, const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx, flint_rand_t randstate)sourceZippel's sparse modular GCD [Zip1979] for A and B in at least two variables that are primitive as polynomials in x_0 over \mathbb{Z}[x_1, \ldots, x_{n-1}]: the GCD modulo one prime fixes the monomials (the shape), and the images modulo further primes are computed by solving for the coefficients of that shape. The coefficients are reconstructed by Chinese remaindering, and the result is verified by division. The bound of fmpz_mpoly_factor_bound_si on the inputs decides when a reconstruction is abandoned.
References#
- [Zip1979] R. Zippel. Probabilistic algorithms for sparse polynomials. Symbolic and Algebraic Computation (EUROSAM 1979), Lecture Notes in Computer Science 72, Springer, 1979, 216–226. https://doi.org/10.1007/3-540-09519-5_73
Cite this page
The FLINT team, “fmpz_mpolyl_gcd_zippel (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_zippel.html (generated 2026-10-20).
@misc{flint-doc-fmpz-mpoly-factor-fmpz-mpolyl-gcd-zippel,
author = {{The FLINT team}},
title = {{fmpz\_mpolyl\_gcd\_zippel (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_zippel.html},
note = {Generated 2026-10-20}
}