DistDeg - Maple Programming Help

DistDeg

distinct degree factorization

 Calling Sequence DistDeg(a, x) mod p DistDeg(a, x, K) mod p

Parameters

 a - univariate polynomial in x x - name K - RootOf p - prime integer

Description

 • 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{\partial }{\partial x}a\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(\mathrm{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(\mathrm{log}[2]\left(p\right){n}^{2}\mathrm{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.

Examples

 > $a≔{x}^{6}+{x}^{5}+{x}^{3}+x$
 ${a}{≔}{{x}}^{{6}}{+}{{x}}^{{5}}{+}{{x}}^{{3}}{+}{x}$ (1)
 > $\mathrm{DistDeg}\left(a,x\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}2$
 $\left[\left[{{x}}^{{2}}{+}{x}{,}{1}\right]{,}\left[{{x}}^{{4}}{+}{x}{+}{1}{,}{4}\right]\right]$ (2)
 > $\mathrm{Factors}\left(a\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}2$
 $\left[{1}{,}\left[\left[{{x}}^{{4}}{+}{x}{+}{1}{,}{1}\right]{,}\left[{x}{,}{1}\right]{,}\left[{x}{+}{1}{,}{1}\right]\right]\right]$ (3)
 > $\mathrm{alias}\left(\mathrm{α}=\mathrm{RootOf}\left({x}^{2}+x+1,x\right)\right):$
 > $a≔{x}^{6}+\mathrm{α}{x}^{5}+{x}^{3}+\mathrm{α}x+x$
 ${a}{≔}{\mathrm{α}}{}{{x}}^{{5}}{+}{{x}}^{{6}}{+}{{x}}^{{3}}{+}{\mathrm{α}}{}{x}{+}{x}$ (4)
 > $\mathrm{DistDeg}\left(a,x,\mathrm{α}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}2$
 $\left[\left[{\mathrm{α}}{}{x}{+}{{x}}^{{2}}{,}{1}\right]{,}\left[{{x}}^{{4}}{+}{\mathrm{α}}{+}{x}{,}{2}\right]\right]$ (5)
 > 

References

 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.