Berlekamp's algorithm: Difference between revisions

Revision as of 15:13, 21 July 2006

Latest revision as of 20:57, 28 July 2025

(64 intermediate revisions by 52 users not shown)

Line 1:

{{Short description|Method in computational algebra}}

{{dablink|This article discusses an algorithm for factorisation of polynomials over finite fields. For the algorithm dealing with LFSRs see [[Berlekamp-Massey algorithm]]}}

{{for|the algorithm dealing with LFSRs|Berlekamp–Massey algorithm}}

In [[mathematics]], particularly [[computer algebra|computational algebra]], '''Berlekamp's algorithm''' is a well -known method for factorising [[polynomial|factoring polynomials]] over [[finite field|finite fields]] (akaalso [[galoisknown as field|''Galois fields]]''). The algorithm consists mainly of [[matrix_matrix (mathematics)|matrix]] reduction and polynomial [[greatest common divisor|GCD]] computations. It was invented by [[Elwyn Berlekamp]] in 1967. It was the dominant algorithm for solving the problem until the [[Cantor-ZassenhausCantor–Zassenhaus algorithm]] algorithm of 1981. It is currently implemented in many well-known [[computer algebra system|computer algebra systems]], including [[PARI-GP_computer_algebra_system|PARI-GP]]s.

==Overview==

Berlekamp's algorithm takes as input a squarfree[[square-free polynomial]] <math>f(x)</math> (i.e. one with no repeated factors) of degree <math>n</math> with coefficients in a finite field <math>\mathbb{F}_q</math> and gives as output a polynomial <math>g(x)</math> with coefficients in the same field such that <math>g(x)</math> divides <math>f(x)</math>. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of <math>f(x)</math> into powers of [[irreducible polynomial|irreducible polynomials]]s (recalling that the [[ring_ring (mathematics)|ring]] of polynomials over a finite field is a [[unique factorisationfactorization ___domain]]).

All possible factors of <math>f(x)</math> are contained within the [[factor ring]]

:<math>R = \frac{\mathbb{F}_q[x]}{\langle f(x) \rangle}.</math>.

The algorithm focuses on polynomials <math>g(x) \in R</math> which satisfy the congruence:

:<math>g(x)^q \equiv g(x) \pmod{f(x)}.\,</math>.

These polynomials form a [[subalgebra]] of R (which can be considered as an <math>n</math> -dimensional vector space over <math>\mathbb{F}_q</math>), called the ''Berlekamp subalgebra''. The Berlekamp subalgebra is of interest because the polynomials <math>g(x)</math> it contains satisfy the result:

:<math>f(x) = \prod_{s \in \mathbb{F}_q} \gcd(f(x),g(x)-s).</math>.

In general, not every GCD in the above product will be a non-trivial factor of <math>f(x)</math>, but some are., providing the factors we seek.

Berlekamp's algorithm finds polynomials <math>g(x)</math> suitable for use with the above result by computing a basis for the Berlekamp subalgebra. This is achieved via the observation that Berlekamp subalgebra is infactin fact the [[nullkernel (linear spacealgebra)|kernel]] of a certain <math>n \times n</math> matrix over <math>\mathbb{F}_q</math>, which is derived from the so-called Berlekamp matrix of the polynomial, denoted <math>\mathcal{Q}</math>. If <math>\mathcal{Q}=[q_{i,j}]</math> then <math>q_{i,j}</math> is the coefficient of the <math>j</math>-th power term in the reduction of <math>x^{iq}</math> modulo <math>f(x)</math>, i.e.:

:<math>x^{iq} \equiv q_{i,n-1}x^{n-1} + q_{i,n-12}x^{n-12} + \ldots + q_{i,0} \pmod{f(x)} .\,</math>.

ForWith a certain polynomial <math>g(x) \in R</math>, say:

:<math>g(x) = g_nxg_{n-1}x^{n-1}+g_{n-12}x^{n-12} + \ldots + g_0, \,</math>

we may associate the row vector:

:<math>g = (g_0, g_1, \ldots, g_ng_{n-1}). \,</math>

It is relatively straightforward to see that the row vector <math>g\mathcal{Q}</math> corresponds, in the same way, to the reduction of <math>g(x)^q</math> modulo <math>f(x)</math>. Consequently, a polynomial <math>g(x) \in R</math> is in the Berlekamp subalgebra if and only if <math>g(\mathcal{Q}-I)=0</math> (where <math>I</math> is the <math>n \times n</math> [[identity matrix]]), i.e. if and only if it is in the null space of <math>\mathcal{Q}-I</math>.

By computing the matrix <math>\mathcal{Q}-I</math> and reducing it to [[reduced row echelon form]] and then easily reading off a basis for the null space, we may find a basis for the Berlekamp subalgebra and hence construct polynomials <math>g(x)</math> in it. We then need to successively compute GCDs of the form above until we find a non-trivial factor. Since the ring of polynomials over a field is a [[Euclidean ___domain]], we may compute these GCDs using the [[Euclidean algorithm]].

==Conceptual algebraic explanation==

With some abstract algebra, the idea behind Berlekamp's algorithm becomes conceptually clear. We represent a finite field <math display = "inline"> \mathbb{F}_q </math>, where <math display="inline"> q = p^m </math> for some prime <math display="inline">p</math>, as <math display = "inline"> \mathbb{F}_p[y]/(g(y)) </math>. We can assume that <math display = "inline"> f(x) \in \mathbb{F}_q[x] </math> is square free, by taking all possible pth roots and then computing the gcd with its derivative.

Now, suppose that <math display = "inline"> f(x) = f_1(x) \ldots f_n(x) </math> is the factorization into irreducibles. Then we have a ring isomorphism, <math display = "inline"> \sigma: \mathbb{F}_q[x]/(f(x)) \to \prod_i \mathbb{F}_q[x]/(f_i(x)) </math>, given by the Chinese remainder theorem. The crucial observation is that the Frobenius automorphism <math display = "inline"> x \to x^p </math> commutes with <math display = "inline"> \sigma </math>, so that if we denote <math display = "inline"> \text{Fix}_p(R) = \{ f \in R : f^p = f \} </math>, then <math display = "inline"> \sigma </math> restricts to an isomorphism <math display = "inline"> \text{Fix}_p( \mathbb{F}_q[x]/(f(x)) ) \to \prod_{i = 1}^n \text{Fix}_p( \mathbb{F}_q[x]/(f_i(x)) ) </math>. By finite field theory, <math display = "inline"> \text{Fix}_p( \mathbb{F}_q[x]/(f_i(x)) )</math> is always the prime subfield of that field extension. Thus, <math display = "inline"> \text{Fix}_p( \mathbb{F}_q[x]/(f(x)) ) </math> has <math display = "inline"> p </math> elements if and only if <math display = "inline"> f(x) </math> is irreducible.

Moreover, we can use the fact that the Frobenius automorphism is <math display = "inline"> \mathbb{F}_p </math>-linear to calculate the fixed set. That is, we note that <math display = "inline"> \text{Fix}_p( \mathbb{F}_q[x]/(f(x)) ) </math> is a <math display = "inline"> \mathbb{F}_p </math>-subspace, and an explicit basis for it can be calculated in the polynomial ring <math display = "inline"> \mathbb{F}_p[x,y]/(f,g) </math> by computing <math display = "inline"> (x^i y^j)^p </math> and establishing the linear equations on the coefficients of <math display = "inline"> x,y </math> polynomials that are satisfied iff it is fixed by Frobenius. We note that at this point we have an efficiently computable irreducibility criterion, and the remaining analysis shows how to use this to find factors.

The algorithm now breaks down into two cases:

* In the case of small <math display = "inline"> p </math> we can construct any <math display = "inline"> g \in \text{Fix}_p( \mathbb{F}_q[x]/(f(x)) ) \setminus \mathbb{F}_p </math>, and then observe that for some <math display = "inline"> a \in \mathbb{F}_p </math> there are <math display = "inline"> i,j </math> so that <math display = "inline"> g - a = 0 \mod f_i</math> and <math display = "inline"> g - a \not = 0 \mod f_j </math>. Such a <math display = "inline"> g - a </math> has a nontrivial factor in common with <math display = "inline"> f(x) </math>, which can be computed via the gcd. As <math display = "inline"> p </math> is small, we can cycle through all possible <math display = "inline"> a </math>.

* For the case of large primes, which are necessarily odd, one can exploit the fact that a random nonzero element of <math display = "inline"> \mathbb{F}_p^* </math> is a square with probability <math display = "inline"> 1/2 </math>, and that the map <math display = "inline"> x \to x^{ \frac{ p -1}{2}} </math> maps the set of non-zero squares to <math display = "inline"> 1 </math>, and the set of non-squares to <math display = "inline"> -1 </math>. Thus, if we take a random element <math display = "inline"> g \in \text{Fix}_p( \mathbb{F}_q[x]/f(x)) </math>, then with good probability <math display = "inline"> g^{ \frac{ p - 1}{2}} - 1 </math> will have a non-trivial factor in common with <math display = "inline"> f(x) </math>.

For further details one can consult.<ref name="Springer">{{cite book | title=Theory of Computation - Dexter Kozen | publisher=Springer | url=https://www.springer.com/gp/book/9781846282973 | access-date=2020-09-19}}</ref>

==Applications==

One important application of Berlekamp's algorithm is in computing [[discrete logarithm|discrete logarithms]]s over finite fields of<math>\mathbb{F}_{p^n}</math>, where <math>p</math> is prime-power orderand <math>n\geq 2</math>. Computing discrete logarithms is an important problem in [[public key cryptography]] and [[Error detection and correction|error-control coding]]. For a fieldfinite of prime-power orderfield, the fastest known method is the [[index calculus|index calculus method]], which involves the factorisation of field elements. If we represent the prime-powerfield order field<math>\mathbb{F}_{p^n}</math> in the usual way - that is, as polynomials over the prime order base field <math>\mathbb{F}_{p}</math>, reduced modulo an irreducible polynomial of appropriate degree <math>n</math> - then this is simply polynomial factorisation, as provided by Berlekamp's algorithm.

==Implementation in Computercomputer Algebraalgebra Systemssystems==

Berlekamp's algorithm may be accessed in the GP-PARI/GP package using the [http://pari.math.u-bordeaux.fr/dochtml/html.-stable/Arithmetic_functions.html#factormod factormod] command, and the [[WolframAlpha]] [http://www.wolframalpha.com/input/?i=factor+x^5+%2B+x+mod+17] website.

==See Alsoalso==

*[[Polynomial factorization|Polynomial factorisation]]

*[[Factorization of polynomials over a finite field and irreducibility tests]]

*[[Cantor-ZassenhausCantor–Zassenhaus algorithm]]

==References==

{{Reflist}}

* Elwyn R. Berlekamp. "Factoring Polynomials Over Finite Fields". Bell Systems Technical Journal, 46:1853-1859, 1967. Later republished in: Elwyn R. Berlekamp. "Algebraic Coding Theory". Mc-Graw Hill, 1968.

*{{Cite journal

|first=Elwyn R.

|last=Berlekamp

|title=Factoring Polynomials Over Finite Fields

|journal=[[Bell System Technical Journal]]

|volume=46

|pages=1853–1859

|year=1967

|issue=8

|mr=0219231

|doi=10.1002/j.1538-7305.1967.tb03174.x}} [http://www.alcatel-lucent.com/bstj/vol46-1967/articles/bstj46-8-1853.pdf BSTJ] Later republished in: {{Cite book |first=Elwyn R. |last=Berlekamp |title=Algebraic Coding Theory |publisher=McGraw Hill |year=1968 |isbn=0-89412-063-8 }}

*{{cite book

|author=Knuth, Donald E

|author-link=Donald E. Knuth

|chapter=4.6.2 Factorization of Polynomials

|title=Seminumerical Algorithms

|series=[[The Art of Computer Programming]]

|volume=2

|edition=Third

|___location=Reading, Massachusetts

|publisher=Addison-Wesley

|year=1997

|pages=439–461, 678–691<!-- xiv+762 -->

|isbn=0-201-89684-2}}

[[Category:Computer Algebraalgebra]]

[[Category:Finite fields]]

[[Category:Polynomial factorization algorithms]]