We describe the functions for polynomial factorization and associated computations. These are available only for a restricted range of coefficient rings.

Subsections

• Factorization and Irreducibility
• Resultant and Discriminant
• Hensel Lifting

    Al: MonStgElt                       Default: "BerlekampSmall"

Given a polynomial p in P[x] in one variable over a ring R, this function returns:

• A factorization sequence Q, that is, a sequence of pairs consisting of an irreducible polynomial q_i (the factor) and a positive integer k_i (the multiplicity);
• A unit u of R

such that p=u.prod_i q_i^(k_i). The unit u will be chosen in an appropriate way; over a field it will be such that q=prod_i q_i^(k_i) is monic, and for R = Z it will equal the sign of the leading coefficient of p.

The coefficient ring R must be one of the following: a finite field F_q, an integer residue class ring Z/pZ with p prime, the ring of integers Z, the field of rationals Q, a rational function field over either Z or Q, or an algebraic number field Q(alpha).

The parameter Al may be used to specify the factorization algorithm for factorizations over finite fields F_q; the possible values are "BerlekampSmall", "BerlekampLarge" and "CantorZassenhaus". Default is "BerlekampSmall" if q < 25, or "BerlekampLarge" otherwise.

Returns the squarefree factorization of the univariate polynomial p in R[x] as a sequence of tuples of length 2, each consisting of a (not necessarily irreducible) factor and an integer indicating the multiplicity. The factors do not contain the square of any polynomial of degree greater than 0. The coefficient ring R must be one of F_q, Z/pZ (with p prime), Z, or a rational function field over either Z or Q.

    Degree: RngIntElt                   Default: 0

Given a square-free univariate polynomial p in F[x] with F a finite field, this function returns the distinct-degree factorization of p as a sequence of tuples of length 2, each consisting of a degree d, together with the product of the degree-d irreducible factors of p.

If the optional parameter Degree is given a value L > 0, then only (products of) factors up to degree L are returned.

Given a univariate polynomial p of degree d over a finite field F this function returns the Berlekamp Q-matrix associated with p, which is an element of the degree d - 1 matrix algebra over F.

Given a polynomial p in R[x] this function returns true if and only p is irreducible over R; here the coefficient ring R must be either a finite field F_q or a ring Z/pZ (with p prime) or Z or Q, or a rational function field over either Z or Q,.

Given a polynomial p in K[x] such that p is irreducible and K is a field, this function returns true iff p is separable.

The discriminant D of p 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 p and the alpha_i are the zeros of p (in some algebraic closure of R). The coefficient ring R must be a domain.

The resultant of univariate polynomials p and q (of degree m and n) in R[x], which is by definition the determinant of the Sylvester matrix for p and q (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 p of degree d over some ring R, return the companion matrix of p as an element of the full matrix algebra of degree d - 1 over R. The companion matrix for p=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