 DistDeg - Maple 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}\phantom{\rule[-0.0ex]{0.4em}{0.0ex}}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.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{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.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}2$
 $\left[{1}{,}\left[\left[{x}{,}{1}\right]{,}\left[{{x}}^{{4}}{+}{x}{+}{1}{,}{1}\right]{,}\left[{x}{+}{1}{,}{1}\right]\right]\right]$ (3)
 > $\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}$ (4)
 > $\mathrm{DistDeg}\left(a,x,\mathrm{\alpha }\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}2$
 $\left[\left[{\mathrm{\alpha }}{}{x}{+}{{x}}^{{2}}{,}{1}\right]{,}\left[{{x}}^{{4}}{+}{\mathrm{\alpha }}{+}{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.