The functions in this section are restricted to univariate polynomials over a field, over the integers, or over a residue class ring of integers with prime modulus, or any polynomial ring over these.
Given univariate polynomials f and g over the ring R, this function returns the greatest common divisor (GCD) of f and g. The valid coefficient rings are those which themselves have a GCD algorithm for their elements (which includes most commutative rings in Magma).If either of the inputs is zero, then the result is the other input (and if the inputs are both zero then the result is zero). The result is normalized (see the function Normalize), so the result is always unique.
For polynomials over finite fields, the simple Euclidean algorithm is used, since this is efficient (there is no intermediate coefficient blowup).
For polynomials over the integers or rationals, a combination of two algorithms is used: (1) the heuristic evaluation `GCDHEU' algorithm of Char et al. ([CGG89] and [GCL92, section 7.7]), suitable for small to moderate-degree dense polynomials; (2) a modular algorithm similar to that presented in [vzGG99, Algorithm 6.38] or [GCL92, section 7.4] (although lifting all the way up to a bound is not used since it is completely unnecessary for correctness in this algorithm!).
For polynomials over an algebraic number field, quadratic field, or cyclotomic field, a fast modular algorithm is used, which maps the field to a residue class polynomial ring modulo a small prime.
Since V2.10, for polynomials over an algebraic function field or polynomial quotient ring over a function field, a new fast modular algorithm of Allan Steel (to be published) is used, which evaluates and interpolates for each base transcendental variable.
For polynomials over another polynomial ring or function field, the polynomials are first "flattened" to be inside a multivariate polynomial ring over the base coefficient ring, then the appropriate (multivariate) algorithm is used for that base coefficient ring.
For polynomials over any other ring, the generic subresultant algorithm [Coh93, section 3.3] is used.
The extended greatest common divisor of polynomials f and g in a univariate polynomial ring P: the function returns polynomials c, a and b in P with deg(a) < deg(g) and deg(b) < deg(f) such that c is the monic GCD of f and g, and c = a.f + b.g. The multipliers a and b are unique if f and g are both non-zero. The coefficient ring must be a field.For polynomials over the rational field, a modular algorithm due to Allan Steel (unpublished) is used; over other fields the basic Euclidean algorithm is used.
The least common multiple of polynomials f and g in a univariate polynomial ring P. The LCM of zero and anything else is zero. The result is normalized (see the function Normalize), so the result is always unique. The valid coefficient rings are as for the function GCD, above.The LCM is effectively computed as Normalize((F div GCD(F, G)) * G), for non-zero inputs.
Given a univariate polynomial f over the ring R, this function returns the unique normalized polynomial g which is associate to f (so g=uf for some unit in R). This is chosen so that if R is a field then g is monic, if R is Z then the leading coefficient of g is positive, if R is a polynomial ring itself, then the leading coefficient of g is recursively normalized, and so on for other rings.
The content of p, that is, the greatest common divisor of the coefficients of p as an element of the coefficient ring.
The primitive part of p, being p divided by the content of p.
The content (the greatest common divisor of the coefficients) of p, as an element of the coefficient ring, as well as the primitive part (p divided by the content) of p.