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 $\mathrm{Gcd}\left(a\,\frac{\ⅆa}{\ⅆx}\right)=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 $\mathrm{O}\left(n^3+{\log }_2\left(p\right)n^2\right)$ 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 $\mathrm{O}\left({\log }_2\left(n\right){\log }_2\left(p\right)n^2+n^3\right)$ 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.

$a≔x^6+x^5+x^4+x^3+2x^2+2x+1$

$a≔x^6+x^5+x^4+x^3+2x^2+2x+1$

$\mathrm{Berlekamp}\left(a\,x\right)\mathbf{mod}2$

$\left\{x^2+x+1\,x^4+x+1\right\}$

$\mathrm{alias}\left(\mathrm{\alpha }=\mathrm{RootOf}\left(x^2+x+1\,x\right)\right)\:$

$\mathrm{Berlekamp}\left(a\,x\,\mathrm{\alpha }\right)\mathbf{mod}2$

$\left\{x+\mathrm{\alpha }\,x+\mathrm{\alpha }+1\,x^2+\mathrm{\alpha }+x\,x^2+\mathrm{\alpha }+x+1\right\}$

$p≔{10}^{10}-33$

$p≔9999999967$

$\mathrm{Berlekamp}\left(x^4+2\,x\right)\mathbf{mod}p$

$\left\{x^2+3027555332x+9284865757\,x^2+6972444635x+9284865757\right\}$

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.