This section describes the functions for polynomial factorization and associated computations. These are available for several kinds of coefficient rings.
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:
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].
- (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.
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.
Given a sequence of tuples, each consisting of pairs of irreducible polynomials and positive integer exponents, return the product polynomial.
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 H43E2 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; 1Now 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; 1We 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; trueSee also Example H43E2 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 discriminant D of f∈R[x] is returned. The discriminant is an element of R that can be defined by D = cn ^ (2n - 2)∏i != j(αi - αj), where cn is the leading coefficient of f and the αi are the zeros of f (in some algebraic closure of R). The coefficient ring R must be a domain.
The resultant of univariate polynomials f and g (of degree m and n) in R[x], which is by definition the determinant of the Sylvester matrix for f and g (a matrix of rank m + n containing coefficients of f and g as entries). The resultant is an element of R. The coefficient ring R must be a domain.
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