Berlekamp - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Algebra : Polynomials : Berlekamp

Berlekamp

distinct degree factorization

 

Calling Sequence

Parameters

Description

Examples

References

Calling Sequence

Berlekamp(a, x) mod p

Berlekamp(a, x, K) mod p

Parameters

a

-

univariate polynomial in x

x

-

name

K

-

a RootOf

p

-

prime integer

Description

• 

This function computes the factorization of a monic square-free univariate polynomial over a finite field GF(p^k) using Berlekamp's algorithm. The factorization is returned as a set of irreducible factors. It is an alternative to the Cantor Zassenhaus distinct degree algorithm which is used by the Factor command.  It is more efficient when p is large and the polynomial is irreducible or has only a few factors.

• 

If the user wants 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 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.

• 

The algorithm used is known as Big Prime Berlekamp because its complexity is good also for large primes.  For the case where the input polynomial is irreducible, the running time of the algorithm is On3+log2pn2 arithmetic operations in GF(p^k). This is better than the Cantor Zassenhaus distinct degree algorithm. However, if the polynomial factors into many factors, these factors must be split using a probabilistic method.  The running time increases to be Olog2nlog2pn2+n3 in the average case.

• 

The implementation uses Maple library code to do the linear algebra.  This is not very efficient for GF(p) where p is small.  The overhead of the Maple interpreter becomes small at about p=10000000000 or in the case of an extension field.

Examples

ax6+x5+x4+x3+2x2+2x+1

ax6+x5+x4+x3+2x2+2x+1

(1)

Berlekampa,xmod2

x2+x+1,x4+x+1

(2)

aliasα=RootOfx2+x+1,x:

Berlekampa,x,αmod2

x+α,x+α+1,x2+α+x,x2+α+x+1

(3)

p101033

p9999999967

(4)

Berlekampx4+2,xmodp

x2+3027555332x+9284865757,x2+6972444635x+9284865757

(5)

References

  

Berlekamp, E.R. "Factoring Polynomials over Large Finite Fields." Mathematics of Computation. 1970. Vol. 24.

  

Geddes, K.O.; Czapor, S.R.; and Labahn, G. Algorithms for Computer Algebra. Kluwer Academic Publishers, 1992.

  

Monagan, M.B. "von zur Gathen's Factorization Challenge." ACM SIGSAM Bulletin, (April 1993): 13-18.

See Also

DistDeg

Factor

Factors

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