|
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.
GreatestCommonDivisor(f, g) : RngUPolElt, RngUPolElt -> RngUPolElt
Gcd(f, g) : RngUPolElt, RngUPolElt -> RngUPolElt
GCD(f, g) : RngUPolElt, RngUPolElt -> RngUPolElt
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.
Xgcd(f, g) : RngUPolElt, RngUPolElt -> RngUPolElt, RngUPolElt, RngUPolElt
XGCD(f, g) : RngUPolElt, RngUPolElt -> RngUPolElt, RngUPolElt, RngUPolElt
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.
Lcm(f, g) : RngUPolElt, RngUPolElt -> RngUPolElt
LCM(f, g) : RngUPolElt, RngUPolElt -> RngUPolElt
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.
Normalize(f) : RngUPolElt -> RngUPolElt
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.
Contpp(p) : RngUPolElt -> RngIntElt, RngUPolElt
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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|