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 $\left[\left[f_1,d_1\right],\dots ,\left[f_m,d_m\right]\right]$ where $a=f_1\cdot \dots \cdot f_m$ and each $f_k$ is a product of $\frac{\mathrm{deg}\left(f_k\right)}{d_k}$ irreducible factors of degree $d_k$.

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 $\mathrm{Gcd}\left(a\,\frac{\ⅆa}{\ⅆx}\right)=1$.

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 $\mathrm{O}\left({\log }_2\left(p\right)n^3\right)$ arithmetic operations in GF(p^k) assuming the use of classical algorithms for polynomial arithmetic.  If there are many factors the complexity improves to $\mathrm{O}\left({\log }_2\left(p\right)n^2{\log }_2\left(n\right)\right)$ 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.

$a≔x^6+x^5+x^3+x$

$a≔x^6+x^5+x^3+x$

$\mathrm{DistDeg}\left(a\,x\right)\mathbf{mod}2$

$\left[\left[x^2+x\,1\right]\,\left[x^4+x+1\,4\right]\right]$

$\mathrm{Factors}\left(a\right)\mathbf{mod}2$

$\left[1\,\left[\left[x^4+x+1\,1\right]\,\left[x+1\,1\right]\,\left[x\,1\right]\right]\right]$

$\mathrm{alias}\left(\mathrm{\alpha }=\mathrm{RootOf}\left(x^2+x+1\,x\right)\right)\:$

$a≔x^6+\mathrm{\alpha }{x}^5+x^3+\mathrm{\alpha }x+x$

$a≔\mathrm{\alpha }{x}^5+x^6+x^3+\mathrm{\alpha }x+x$

$\mathrm{DistDeg}\left(a\,x\,\mathrm{\alpha }\right)\mathbf{mod}2$

$\left[\left[\mathrm{\alpha }x+x^2\,1\right]\,\left[x^4+\mathrm{\alpha }+x\,2\right]\right]$

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.