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.

[0] gcd(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
x^3+3*x^2+3*x+1
[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
[2] gcd((x+y)*(x-y)^2,(x+y)^2*(x-y));
x^2-y^2
[3] 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.