n_bpoly_mod_gcd_brown_smprime
Synopsis
#include <flint/n_poly.h>int n_bpoly_mod_gcd_brown_smprime(n_bpoly_t G, n_bpoly_t Abar, n_bpoly_t Bbar, n_bpoly_t A, n_bpoly_t B, nmod_t ctx, n_poly_bpoly_stack_t Sp)sourceBrown's dense modular GCD algorithm [Bro1971] for bivariate polynomials over a word-size prime field: evaluates y at pairs of points \pm \alpha, computes univariate GCDs and interpolates. Sets G = \gcd(A, B), \bar A = A/G, \bar B = B/G and returns 1, or returns 0 if it ran out of evaluation points (the prime is too small). A and B are clobbered. Sp provides the temporaries. See Multivariate polynomials: representations and algorithms.
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, “n_bpoly_mod_gcd_brown_smprime (n_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/n_poly/n_bpoly_mod_gcd_brown_smprime.html (generated 2026-10-20).
@misc{flint-doc-n-poly-n-bpoly-mod-gcd-brown-smprime,
author = {{The FLINT team}},
title = {{n\_bpoly\_mod\_gcd\_brown\_smprime (n\_poly.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/n_poly/n_bpoly_mod_gcd_brown_smprime.html},
note = {Generated 2026-10-20}
}