DistDeg - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

DistDeg

distinct degree factorization

 

Calling Sequence

Parameters

Description

Examples

References

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 Olog[2]pn3 arithmetic operations in GF(p^k) assuming the use of classical algorithms for polynomial arithmetic.  If there are many factors the complexity improves to Olog[2]pn2log[2]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.

Examples

ax6+x5+x3+x

ax6+x5+x3+x

(1)

DistDega,xmod2

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

(2)

Factorsamod2

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

(3)

aliasα=RootOfx2+x+1,x:

ax6+αx5+x3+αx+x

aαx5+x6+x3+αx+x

(4)

DistDega,x,αmod2

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

(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.

See Also

Berlekamp

Factor

Factors

ProbSplit

RootOf

Sqrfree

 


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