DistDeg
distinct degree factorization
Calling Sequence
Parameters
Description
Examples
References
DistDeg(a, x) mod p
DistDeg(a, x, K) mod p
a
-
univariate polynomial in x
x
name
K
RootOf
p
prime integer
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
DistDeg⁡a,xmod2
x2+x,1,x4+x+1,4
Factors⁡amod2
1,x,1,x+1,1,x4+x+1,1
alias⁡α=RootOf⁡x2+x+1,x:
a ≔ x6+α⁢x5+x3+α⁢x+x
a≔α⁢x5+x6+x3+α⁢x+x
DistDeg⁡a,x,αmod2
α⁢x+x2,1,x4+α+x,2
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.
See Also
Berlekamp
Factor
Factors
ProbSplit
Sqrfree
Download Help Document
What kind of issue would you like to report? (Optional)