|
This section describes the functions for polynomial factorization
and associated computations.
These are available for several kinds of coefficient rings.
Factorization(f) : RngUPolElt -> [ < RngUPolElt, RngIntElt >], RngElt
Factorisation(f) : RngUPolElt -> [ < RngUPolElt, RngIntElt >], RngElt
Al: MonStgElt Default: "Default"
Given a univariate polynomial f over the ring R, this function returns
the factorization of f as a factorization sequence Q,
that is, a sequence of pairs, each consisting of an irreducible
factor qi a positive integer ki (its multiplicity).
Each irreducible factor is normalized (see the function
Normalize), so the expansion of the factorization
sequence is the unique canonical associate of f.
The function also returns the unit u of R giving the normalization, so
f=u.∏i qiki.
The coefficient ring R must be one of the following: a finite field
Fq, the ring of integers Z, the field of rationals Q, an
algebraic number field Q(α), a local ring, or a polynomial
ring, function field (rational or algebraic) or
finite-dimensional affine algebra (which is a field) over any of the above.
For factorization over very small finite fields, the Berlekamp
algorithm is used by default, which depends on fast linear algebra (see, for
example, [Knu97, section 4.6.2] or [vzGG99, section 14.8]).
For medium to large finite fields, the von zur Gathen/Kaltofen/Shoup algorithm
([vzGS92], [KS95], [Sho95]) is used by
default. The parameter Al may be used to specify the
factorization algorithm over finite fields. The possible values are:
- (1)
- "Default": The default strategy, whereby an appropriate
choice will be made.
- (2)
- "BerlekampSmall" or "BerlekampLarge" for the Berlekamp
algorithm (see [Knu97, pp. 446--447] for the difference between
these two variants).
- (3)
- "GKS" for the von zur Gathen/Kaltofen/Shoup algorithm.
Since V2.8 (July 2001), Magma uses the algorithm of
Mark van Hoeij [vH02], [vH01] to factor polynomials over the
integers or rationals. First a factorization of f is found modulo a
suitable small prime, then Hensel lifting is applied, as in the
standard Berlekamp-Zassenhaus (BZ) algorithm [Knu97, p. 452].
The Hensel lifting is performed using Victor Shoup's `tree lifting' algorithm,
as described in [vzGG99, Sec. 15.5].
Easy factors are also detected at various stages, if possible, using heuristics
developed by Allan Steel.
But the final search for the correct combination of modular factors
(which has exponential worst-case complexity in the standard BZ
algorithm) is now performed by van Hoeij's algorithm, which efficiently
finds the correct combinations by solving a Knapsack problem via the
LLL lattice-basis reduction algorithm [LLL82].
van Hoeij's new algorithm is much more efficient in practice than
the original lattice-based factoring algorithm proposed in [LLL82]:
the lattice constructed in van Hoeij's algorithm has dimension equal to
the number of modular factors (not the degree of the input polynomial),
and the entries of the lattice are very much smaller. Many polynomials
can now be easily factored which were out of reach for any previous
algorithm (see the examples below).
For polynomials over algebraic number fields, algebraic function fields and
affine algebras, the norm-based algorithm of Trager
[Tra76] is used, which performs a suitable
substitution and resultant computation, and then factors the resulting
polynomial with one less variable. In characteristic zero, the
difficult case (where there are very many factors of this integral
polynomial modulo any prime) is now easily handled by van Hoeij's
combination algorithm above. In small characteristic, where
inseparable field extensions may occur, an algorithm of Allan Steel
([Ste05]) is used.
Given a ring R, return whether factorization of polynomials
over R is allowed in Magma.
(Procedure.)
Change the verbose printing level for all polynomial factorization
algorithms to be v. Currently the legal levels are 0, 1, 2 or 3.
Facpol(f) : [Tup] -> BoolElt
Given a sequence of tuples, each consisting of pairs of irreducible polynomials
and positive integer exponents, return the product polynomial.
To demonstrate the power of the van Hoeij combination algorithm,
in this example we factor Swinnerton-Dyer polynomials, which
are worse-case inputs for the Berlekamp-Zassenhaus factorization
algorithm for polynomials over Z.
The n-th Swinnerton-Dyer polynomial is defined to be
∏(x ∓ Sqrt(2) ∓ Sqrt(3) ∓ Sqrt(5) ∓ ... ∓ Sqrt(pn)),
where pi is the i-th prime and the product runs over all 2n
possible combinations of + and - signs. This polynomial lies in
Z[x], has degree 2n, is irreducible over Z, and has at least
2n - 1 factors modulo any prime. This last fact is easy to see, since,
given any finite field K, the polynomial must split into linear factors
over a quadratic
extension of K, so it will have only linear or quadratic factors over
K. See also [vzGG99, section 15.3] for further discussion.
In this example, we use the function SwinnertonDyerPolynomial
to construct the polynomials (see Example H44E2 in the
chapter on algebraically closed fields for an explanation of how
this function works).
First we display the first 4 polynomials.
> P<x> := PolynomialRing(IntegerRing());
> SwinnertonDyerPolynomial(1);
x^2 - 2
> SwinnertonDyerPolynomial(2);
x^4 - 10*x^2 + 1
> SwinnertonDyerPolynomial(3);
x^8 - 40*x^6 + 352*x^4 - 960*x^2 + 576
> SwinnertonDyerPolynomial(4);
x^16 - 136*x^14 + 6476*x^12 - 141912*x^10 + 1513334*x^8 - 7453176*x^6 +
13950764*x^4 - 5596840*x^2 + 46225
> IsIrreducible($1);
true
We note the degree patterns of the factorizations of the first
eight Swinnerton-Dyer polynomials over the three finite fields GF(3),
GF(23) and GF(503). There are only linear or quadratic factors,
as expected.
> for i := 1 to 8 do
> f := SwinnertonDyerPolynomial(i);
> printf "%o:", i;
> for p in [3, 23, 503] do
> L := Factorization(PolynomialRing(GF(p)) ! f);
> printf " %o", {* Degree(t[1])^^t[2]: t in L *};
> end for;
> "";
> end for;
1: {* 2 *} {* 1^^2 *} {* 1^^2 *}
2: {* 2^^2 *} {* 1^^4 *} {* 1^^4 *}
3: {* 1^^4, 2^^2 *} {* 2^^4 *} {* 2^^4 *}
4: {* 1^^8, 2^^4 *} {* 2^^8 *} {* 2^^8 *}
5: {* 1^^8, 2^^12 *} {* 2^^16 *} {* 2^^16 *}
6: {* 1^^16, 2^^24 *} {* 2^^32 *} {* 2^^32 *}
7: {* 1^^48, 2^^40 *} {* 2^^64 *} {* 2^^64 *}
8: {* 1^^96, 2^^80 *} {* 1^^16, 2^^120 *} {* 2^^128 *}
We now construct the 6-th polynomial, note its largest coefficient, and then
factor it; it takes only a second to prove that it is irreducible,
even though there are 32 modular factors.
> sd6 := SwinnertonDyerPolynomial(6);
> Degree(sd6);
64
> Max([Abs(x): x in Coefficients(sd6)]);
1771080720430629161685158978892152599456 11
> time L := Factorization(sd6);
Time: 1.009
> #L;
1
Now we factor the 7-th polynomial!
> sd7 := SwinnertonDyerPolynomial(7);
> Degree(sd7);
128
> Max([Abs(x): x in Coefficients(sd7)]);
8578344714036018778166274416336425267466563380359649680696924587\
44011458425706833248256 19
> time L := Factorization(sd7);
Time: 11.670
> #L;
1
We now factor the product of the 6-th and 7-th polynomials. This
has degree 192 and has at least 96 factors modulo any prime! But
the van Hoeij algorithms easily finds the correct factors over the integers.
> p := sd6*sd7;
> Degree(p);
192
> Max([Abs(x): x in Coefficients(p)]);
4617807523303144159751988353619837233948679680057885997820625979\
481789171112550210109817070112666284891955285248592492005163008
31
> time L := Factorization(p);
Time: 16.840
> #L;
2
> L[1,1] eq sd6;
true
> L[2,1] eq sd7;
true
See also Example H44E2 in the chapter on algebraically closed fields
for a generalization of the Swinnerton-Dyer polynomials.
Given a univariate polynomial f over the ring R, this function returns
the squarefree factorization of f as a sequence of pairs,
each consisting of a (not necessarily irreducible) factor and an
integer indicating the multiplicity. The factors do not contain
the square of any non-constant polynomial.
The coefficient ring R must be the integer ring or any field.
The algorithm works by computing the GCD of f with its
derivative and repeating as necessary (special considerations
are also necessary for characteristic p).
Degree: RngIntElt Default: 0
Given a squarefree univariate polynomial f∈F[x] with F a finite field,
this function returns the distinct-degree factorization of f as a sequence of
pairs, each consisting of a degree d, together with the product of the
degree-d irreducible factors of f.
If the optional parameter Degree is given a value L > 0, then only
(products of) factors up to degree L are returned.
Given a squarefree univariate polynomial f∈F[x] with F a finite field,
and integer d and another polynomial g∈F[x] such that F is known
to be the product of distinct degree-d irreducible polynomials alone,
and g is xq mod f, where q is the cardinality of F,
this function returns the irreducible factors of f as a sequence of
polynomials (no multiplicities are needed).
If the conditions are not satisfied, the result is unpredictable.
This function allows one to split f, assuming that one has computed
f in some special way.
Given a univariate polynomial f over the ring R, this function returns
returns true if and only f is irreducible over R.
The conditions on R are the same as for the function
Factorization above.
Given a polynomial f∈K[x]
such that f is a polynomial of degree ≥1 and K is a field
allowing polynomial factorization,
this function returns true iff f is separable.
Given a univariate polynomial f of degree d over a finite field F
this function returns the Berlekamp Q-matrix associated with f,
which is an element of the degree d - 1 matrix algebra over F.
The Sylvester matrix of univariate polynomials f and g
(of degree m and n respectively).
This is an (m + n) x (m + n) matrix with entries
in R, which
is constructed by first creating n rows from the coefficients of f,
followed by m rows from the coefficients of g.
Within the two above blocks for rows, each subsequent row is a shifted
version of the row above, with zeros filling in the empty spaces.
The coefficient ring R may be any ring.
The resultant of univariate polynomials f and g
(of degree m and n respectively) in R[x],
which is by definition the determinant
of the Sylvester matrix of f and g.
The resultant is an element of R.
The coefficient ring R may be any commutative ring.
The discriminant D of f∈R[x], where R is any commutative ring.
This is an element of R that is exactly equivalent
to the Magma call:
LeadingCoefficient(f)^(Degree(f) - Degree(d) - 2) *
Resultant(f, d)
where d := Derivative(f).
Given a monic univariate polynomial f of degree d
over some ring R, return the companion matrix of f as an
element of the full matrix algebra of degree d - 1 over R. The companion
matrix for f=a0 + a1x + ... + ad - 1xd - 1 + xd is given by
[ 0 1 0 ... 0 ]
[ 0 0 1 ... 0 ]
[ . . . . . ]
[ . . . . . ]
[ . . . . . ]
[ -a_0 -a_1 -a_2 ... -a_(d-1) ]
Given the sequence of irreducible factors s modulo some prime p
of the univariate integer polynomial f, return the Hensel lifting into
the polynomial ring P, which must be the univariate polynomial
ring over a residue class ring modulo some power of p. Thus
given f ≡ ∏i si mod p, this returns f ≡ ∏i ti mod pk
for some k ≥1, as a sequence of polynomials in Z/pkZ.
The factorization of f modulo p must be squarefree, that is, s
should not contain repeated factors.
> R<x> := PolynomialRing(Integers());
> b := x^5 - x^3 + 2*x^2 - 2;
> F<f> := PolynomialRing(GF(5));
> s := [ w[1] : w in Factorization( F ! b ) ];
> s;
[
f + 1,
f + 3,
f + 4,
f^2 + 2*f + 4
]
> T<t> := PolynomialRing(Integers(5^3));
> h := HenselLift(b, s, T);
> h;
[
t + 1,
t + 53,
t + 124,
t^2 + 72*t + 59
]
> &*h;
t^5 + 124*t^3 + 2*t^2 + 123
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|