Berlekamp
distinct degree factorization
Calling Sequence
Parameters
Description
Examples
References
Berlekamp(a, x) mod p
Berlekamp(a, x, K) mod p
a

univariate polynomial in x
x
name
K
a RootOf
p
prime integer
This function computes the factorization of a monic squarefree 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 squarefree, 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 squarefree is $\mathrm{Gcd}\left(a\,\frac{\partial}{\partial x}\phantom{\rule[0.0ex]{0.4em}{0.0ex}}a\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}+{\mathrm{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({\mathrm{log}}_{2}\left(n\right){\mathrm{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\u2254{x}^{6}+{x}^{5}+{x}^{4}+{x}^{3}+2{x}^{2}+2x+1$
${a}{\u2254}{{x}}^{{6}}{+}{{x}}^{{5}}{+}{{x}}^{{4}}{+}{{x}}^{{3}}{+}{2}{}{{x}}^{{2}}{+}{2}{}{x}{+}{1}$
$\mathrm{Berlekamp}\left(a\,x\right)\phantom{\rule[0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[0.0ex]{0.3em}{0.0ex}}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)\phantom{\rule[0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[0.0ex]{0.3em}{0.0ex}}2$
$\left\{{x}{+}{\mathrm{\alpha}}{\,}{x}{+}{\mathrm{\alpha}}{+}{1}{\,}{{x}}^{{2}}{+}{\mathrm{\alpha}}{+}{x}{\,}{{x}}^{{2}}{+}{\mathrm{\alpha}}{+}{x}{+}{1}\right\}$
$p\u2254{10}^{10}33$
${p}{\u2254}{9999999967}$
$\mathrm{Berlekamp}\left({x}^{4}+2\,x\right)\phantom{\rule[0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[0.0ex]{0.3em}{0.0ex}}p$
$\left\{{{x}}^{{2}}{+}{3027555332}{}{x}{+}{9284865757}{\,}{{x}}^{{2}}{+}{6972444635}{}{x}{+}{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): 1318.
See Also
DistDeg
Factor
Factors
RootOf
Sqrfree
Download Help Document
What kind of issue would you like to report? (Optional)