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 q_i a positive integer k_i (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⋅prod_i q_i^(k_i).The coefficient ring R must be one of the following: a finite field F_q, the ring of integers Z, the field of rationals Q, an algebraic number field Q(alpha), a local ring, or a polynomial ring, rational function field or finite-dimensional affine algebra 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 cite[section 14.8] {GathenGerhard}). 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 exciting new algorithm of Mark van Hoeij [vH01b], [vH01a] 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].
- "Default": The default strategy, whereby an appropriate choice will be made.
- "BerlekampSmall" or "BerlekampLarge" for the Berlekamp algorithm (see [Knu97, pp. 446--447] for the difference between these two variants).
- "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 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 integral univariate polynomial. 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, so this algorithm runs in polynomial time in all cases.
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.
The n-th Swinnerton-Dyer polynomial is defined to be prod (x +- Sqrt(2) +- Sqrt(3) +- Sqrt(5) +- ... +- Sqrt(p_n)), where p_i is the i-th prime and the product runs over all 2^n possible combinations of + and - signs. This polynomial lies in Z[x], has degree 2^n, is irreducible over Z, and has at least 2^(n - 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 H56E2 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!
> 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 H56E2 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 in 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 in F[x] with F a finite field, and integer d and another polynomial g in F[x] such that F is known to be the product of distinct degree-d irreducible polynomials alone, and g is x^q 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 p in K[x] such that f is irreducible and K is a field, 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 in R[x] is returned. The discriminant is an element of R that can be defined by D = c_n ^ (2n - 2)prod_(i != j)(alpha_i - alpha_j), where c_n is the leading coefficient of f and the alpha_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=a_0 + a_1x + ... + a_(d - 1)x^(d - 1) + x^d 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 p, 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 = prod_is_i mod p, this returns f = prod_it_i mod p^k for some k >= 1, as a sequence of polynomials in Z/p^kZ. 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