Go to the first, previous, next, last section, table of contents.

### `gcd`, `gcdz`

gcd(poly1,poly2[,mod])
gcdz(poly1,poly2)
:: The polynomial greatest common divisor of poly1 and poly2.
return
polynomial
poly1,poly2
polynomial
mod
prime
• Functions `gcd()` and `gcdz()` return the greatest common divisor (GCD) of the given two polynomials.
• Function `gcd()` returns an integral polynomial GCD over the rational number field. The coefficients are normalized such that their GCD is 1. It returns 1 in case that the given polynomials are mutually prime.
• Function `gcdz()` works for arguments of integral polynomials, and returns a polynomial GCD over the integer ring, that is, it returns `gcd()` multiplied by the contents of all coefficients of the two input polynomials.
• `gcd()` computes the GCD over GF(mod) if mod is specified.
• Polynomial GCD is computed by an improved algorithm based on Extended Zassenhaus algorithm.
• GCD over a finite field is computed by PRS algorithm and it may not be efficient for large inputs and co-prime inputs.
``` gcd(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
x^3+3*x^2+3*x+1
 gcdz(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
6*x^3+18*x^2+18*x+6
 gcd((x+y)*(x-y)^2,(x+y)^2*(x-y));
x^2-y^2
 gcd((x+y)*(x-y)^2,(x+y)^2*(x-y),2);
x^3+y*x^2+y^2*x+y^3
```
References
section `igcd`,`igcdcntl`.

Go to the first, previous, next, last section, table of contents.