The command RegularGcd(p1, p2, v, rc, R) returns a list of pairs $\left[g_i\,{\mathrm{rc}}_i\right]$ where $g_i$ is a non-zero polynomial of R and ${\mathrm{rc}}_i$ is a regular chain of $R$.

$v$ must be the common main variable of p1 and p2.

The initials of p1 and p2 must be regular with respect to rc.  In order to check this condition, use the command IsRegular. If condition does not hold, then the command RegularizeInitial must be used to split the problem into sub-problems where all the requirements are met.

For each returned pair, the polynomial $g_i$ is a GCD of p1 and p2 modulo the saturated ideal of ${\mathrm{rc}}_i$, in the following sense. First, the leading coefficient of the polynomial $g_i$ with respect to v is regular modulo the saturated ideal of ${\mathrm{rc}}_i$. Secondly, the polynomial $g_i$ belongs to the ideal generated by p1 and p2 and the saturated ideal of ${\mathrm{rc}}_i$. Thirdly, if the polynomial $g_i$ has positive degree with respect to v, then the pseudo-remainders of both p1 and p2 by $g_i$ are null modulo the the saturated ideal of ${\mathrm{rc}}_i$. This idea of polynomial GCD modulo the saturated ideal of a regular chain extends the usual notion of polynomial GCDs to non-integral domains.

The returned regular chains ${\mathrm{rc}}_i$ form a triangular decomposition of rc in the sense of Kalkbrener. See the page RegularChains for the concept of a triangular decomposition.

If the option 'normalized'='yes' is present, then the returned regular chains are normalized. See ChainTools for the concepts of normalized and strongly normalized regular chain.

If 'normalized'='yes' is present, then rc must be normalized.

If the option 'normalized'='strongly' is present, then the returned regular chains are strongly normalized.

If 'normalized'='strongly' is present, then rc must be strongly normalized.

For more details on the specifications and the algorithm, refer to the paper "On triangular decompositions of algebraic varieties" by M. Moreno Maza, available at the author's web page.

The command RegularGcd(src, rc, R) has the same specification as RegularGcd(p1, p2, v, rc, R) where src is the subresultant chain returned by SubresultantChain(f1, f2, v, R). In this case, the algorithm is that of X. Li, M. Moreno Maza and W. Pan from the paper "Computations modulo regular chains". This requires that the resultant of f1 and f2 is zero modulo the saturated ideal of this regular chain. See the command SubresultantChain for details and an example.

When R has prime characteristic, an algorithm based on modular techniques and asymptotically fast polynomial arithmetic is available through the command RegularGcdBySpecializationCube. Here again the reference is "Computations modulo regular chains" by X. Li, M. Moreno Maza and W. Pan.

$\mathrm{with}\left(\mathrm{RegularChains}\right)\:$$\mathrm{with}\left(\mathrm{ChainTools}\right)\:$

$R≔\mathrm{PolynomialRing}\left(\left[y\,x\right]\right)$

$R≔\mathrm{polynomial\_ring}$

$\mathrm{rc}≔\mathrm{Chain}\left(\left[x^2+1\right]\,\mathrm{Empty}\left(R\right)\,R\right)$

$\mathrm{rc}≔\mathrm{regular\_chain}$

$\mathrm{p1}≔\mathrm{expand}\left(\left(\left(x+1\right)y+x\right)\left(y+1\right)\right)$

$\mathrm{p1}≔x{y}^2+2yx+y^2+x+y$

$\mathrm{p2}≔\mathrm{expand}\left(\left(\left(x-1\right)y+x\right)\left(y+1\right)\right)$

$\mathrm{p2}≔x{y}^2+2yx-y^2+x-y$

$\mathrm{out}≔\mathrm{RegularGcd}\left(\mathrm{p1}\,\mathrm{p2}\,y\,\mathrm{rc}\,R\right)\;$$\mathrm{factor}\left(\mathrm{out}\left[1\right]\left[1\right]\right)$

$\mathrm{out}≔\left[\left[2xy+2x\,\mathrm{regular\_chain}\right]\right]$

$2x\left(y+1\right)$

$R≔\mathrm{PolynomialRing}\left(\left[z\,y\,x\right]\right)$

$R≔\mathrm{polynomial\_ring}$

$\mathrm{mx}≔x^2-2$

$\mathrm{mx}≔x^2-2$

$\mathrm{rc}≔\mathrm{Chain}\left(\left[\mathrm{mx}\right]\,\mathrm{Empty}\left(R\right)\,R\right)$

$\mathrm{rc}≔\mathrm{regular\_chain}$

$\mathrm{my}≔\mathrm{expand}\left(\left(y-x\right)\left(y+x-1\right)\right)$

$\mathrm{my}≔-x^2+y^2+x-y$

$\mathrm{my}≔\mathrm{SparsePseudoRemainder}\left(\mathrm{my}\,\mathrm{rc}\,R\right)$

$\mathrm{my}≔y^2+x-y-2$

$\mathrm{rc}≔\mathrm{Chain}\left(\left[\mathrm{my}\right]\,\mathrm{rc}\,R\right)$

$\mathrm{rc}≔\mathrm{regular\_chain}$

$\mathrm{p1}≔\left(y-x\right)z+\left(y+x-1\right)\left(z+1\right)$

$\mathrm{p1}≔\left(y-x\right)z+\left(y+x-1\right)\left(z+1\right)$

$\mathrm{p2}≔\left(y-x\right)\cdot 1+\left(y+x-1\right)\left(z+1\right)$

$\mathrm{p2}≔y-x+\left(y+x-1\right)\left(z+1\right)$

$\mathrm{out\_gcd}≔\mathrm{RegularGcd}\left(\mathrm{p1}\,\mathrm{p2}\,z\,\mathrm{rc}\,R\right)$

$\mathrm{out\_gcd}≔\left[\left[\left(y+x-1\right)z+2y-1\,\mathrm{regular\_chain}\right]\,\left[3y^2+\left(-2x-2\right)y-x^2+2x\,\mathrm{regular\_chain}\right]\right]$

Kalkbrener, M. "A generalized Euclidean algorithm for computing triangular representations of algebraic varieties." J. Symb. Comp., Vol. 15. (1993): 143-167.

Moreno Maza, M. "On Triangular Decompositions of Algebraic Varieties." MEGA-2000 conference. Bath, UK, England.

Moreno Maza, M. and Rioboo, R. "Polynomial GCD computations over towers of algebraic extensions" In proc. of AAECC-11, Lecture Notes in Comput. Sci, Vol. 948, Springer, 1995.

X. Li, M. Moreno Maza and W. Pan. "Computations modulo regular chains." In proc. of ISSAC 2009, ACM Press.