distinct degree factorization - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Group Theory : Inert Functions : DistDeg

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 f1,d1,,fm,dm where a=f1fm and each fk is a product of degfkdk 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 Gcda,xa=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 Olog2pn3 arithmetic operations in GF(p^k) assuming the use of classical algorithms for polynomial arithmetic.  If there are many factors the complexity improves to Olog2pn2log2n 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:=x6+x5+x3+x

a:=x6+x5+x3+x

(1)

DistDega,xmod2

x2+x,1,x4+x+1,4

(2)

Factorsamod2

1,x+1,1,x4+x+1,1,x,1

(3)

aliasα=RootOfx2+x+1,x:

a:=x6+αx5+x3+αx+x

a:=αx5+x6+x3+αx+x

(4)

DistDega,x,αmod2

αx+x2,1,x4+α+x,2

(5)

See Also

Berlekamp, Factor, Factors, ProbSplit, RootOf, Sqrfree

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.


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam