distinct degree factorization
DistDeg(a, x) mod p
DistDeg(a, x, K) mod p
univariate polynomial in x
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 f1,d1,…,fm,dm where a=f1⁢⋅⁢…⁢⋅fm and each fk is a product of deg⁡fkdk irreducible factors of degree dk.
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 Gcd⁡a,ⅆaⅆx=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 O⁡log2⁡p⁢n3 arithmetic operations in GF(p^k) assuming the use of classical algorithms for polynomial arithmetic. If there are many factors the complexity improves to O⁡log2⁡p⁢n2⁢log2⁡n 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 ≔ x6+x5+x3+x
a ≔ x6+α⁢x5+x3+α⁢x+x
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.
Download Help Document