Berlekamp's algorithm: Difference between revisions

Revision as of 18:33, 21 July 2006

Revision as of 03:25, 22 July 2006

Line 1:

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

In [[mathematics]], particularly [[computer algebra|computational algebra]], Berlekamp's algorithm is a well -known method for factorising [[polynomial|polynomials]]s over [[finite field|finite fields]]s (akaalso [[galoisknown field|as ''Galois fields]]''). The algorithm consists mainly of [[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-Zassenhaus Algorithm|Cantor-Zassenhaus 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]].

==Overview==

Berlekamp's algorithm takes as input a squarfreesquare-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]] (recalling that the [[ring_(mathematics)|ring]] of polynomials over a finite field is a [[unique factorisation ___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 [[null space]] 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}x^n + q_{i,n-1}x^{n-1} + \ldots + q_{i,0} \pmod{f(x)} </math>.

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

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

we may associate the row vector:

:<math>g = (g_0, g_1, \ldots, g_n). </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]].

==Applications==

Line 40:

==See Also==

*[[Polynomial factorization|Polynomial factorisation]]

*[[Cantor-Zassenhaus Algorithmalgorithm]]

==References==