This function computes the distinct degree factorization of a monic square-free univariate polynomial over a finite field. The factorization is returned as a list of pairs of the form  where  and each  is a product of  irreducible factors of degree .

If the user needs to factor a polynomial which is not monic and square-free, i.e. the leading coefficient is not 1, or there are repeated factors,  then the user should apply the Sqrfree function first.  Note, the condition that a polynomial be square-free is .

The Split function can be applied to the resulting factors of DistDeg to split them into irreducible factors.

The optional argument K specifies an extension field over which the factorization is to be done.  See Factor for further information. Note: only the case of a single field extension is implemented.

Algorithm: The algorithm used is the Cantor-Zassenhaus distinct degree factorization.  The average case complexity depends on the number of factors.  If the polynomial is irreducible, the complexity is  arithmetic operations in GF(p^k) assuming the use of classical algorithms for polynomial arithmetic.  If there are many factors the complexity improves to  in the best case.

Implementation: The implementation for the case GF(p) is largely in C. See the modp1 package for details.  For the case GF(p^k), the implementation is in Maple but arithmetic in GF(p^k) is done largely in C using the modp1 package.

Cantor, D.G., and Zassenhaus, H. "A New Algorithm for Factoring Polynomials over a Finite Field." Mathematics of Computation, (1981): 587-592.

Geddes, K.O.; Czapor, S.R.; and Labahn, G. Algorithms for Computer Algebra. Kluwer Academic Publishers, 1992.