Berlekamp's algorithm

For the algorithm dealing with LFSRs, see Berlekamp–Massey algorithm.

In mathematics, particularly computational algebra, Berlekamp's algorithm is a well-known method for factoring polynomials over finite fields (also known as Galois fields). The algorithm consists mainly of matrix reduction and polynomial GCD computations. It was invented by Elwyn Berlekamp in 1967. It was the dominant algorithm for solving the problem until the Cantor–Zassenhaus algorithm of 1981. It is currently implemented in many well-known computer algebra systems, including PARI/GP.

Overview

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

All possible factors of ${\displaystyle f(x)}$  are contained within the factor ring

${\displaystyle R={\frac {\mathbb {F} _{q}[x]}{\langle f(x)\rangle }}.}$ 

The algorithm focuses on polynomials ${\displaystyle g(x)\in R}$  which satisfy the congruence:

${\displaystyle g(x)^{q}\equiv g(x){\pmod {f(x)}}.\,}$ 

These polynomials form a subalgebra of R (which can be considered as an ${\displaystyle n}$ -dimensional vector space over ${\displaystyle \mathbb {F} _{q}}$ ), called the Berlekamp subalgebra. The Berlekamp subalgebra is of interest because the polynomials ${\displaystyle g(x)}$  it contains satisfy

${\displaystyle f(x)=\prod _{s\in \mathbb {F} _{q}}\gcd(f(x),g(x)-s).}$ 

In general, not every GCD in the above product will be a non-trivial factor of ${\displaystyle f(x)}$ , but some are, providing the factors we seek.

Berlekamp's algorithm finds polynomials ${\displaystyle g(x)}$  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 in fact the kernel of a certain ${\displaystyle (n+1)\times (n+1)}$  matrix over ${\displaystyle \mathbb {F} _{q}}$ , which is derived from the so-called Berlekamp matrix of the polynomial, denoted ${\displaystyle {\mathcal {Q}}}$ . If ${\displaystyle {\mathcal {Q}}=[q_{i,j}]}$  then ${\displaystyle q_{i,j}}$  is the coefficient of the ${\displaystyle j}$ -th power term in the reduction of ${\displaystyle x^{iq}}$  modulo ${\displaystyle f(x)}$ , i.e.:

${\displaystyle x^{iq}\equiv q_{i,n}x^{n}+q_{i,n-1}x^{n-1}+\ldots +q_{i,0}{\pmod {f(x)}}.\,}$ 

With a certain polynomial ${\displaystyle g(x)\in R}$ , say:

${\displaystyle g(x)=g_{n}x^{n}+g_{n-1}x^{n-1}+\ldots +g_{0},\,}$ 

we may associate the row vector:

${\displaystyle g=(g_{0},g_{1},\ldots ,g_{n}).\,}$ 

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

By computing the matrix ${\displaystyle {\mathcal {Q}}-I}$  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 ${\displaystyle g(x)}$  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

One important application of Berlekamp's algorithm is in computing discrete logarithms over finite fields ${\displaystyle \mathbb {F} _{p^{n}}}$ , where ${\displaystyle p}$  is prime and ${\displaystyle n\geq 2}$ . Computing discrete logarithms is an important problem in public key cryptography. For a finite field, the fastest known method is the index calculus method, which involves the factorisation of field elements. If we represent the field ${\displaystyle \mathbb {F} _{p^{n}}}$  in the usual way - that is, as polynomials over the base field ${\displaystyle \mathbb {F} _{p}}$ , reduced modulo an irreducible polynomial of degree ${\displaystyle n}$  - then this is simply polynomial factorisation, as provided by Berlekamp's algorithm.

Implementation in Computer Algebra Systems

Berlekamp's algorithm may be accessed in the PARI/GP package using the factormod command.

See also

• Polynomial factorisation
• Factorization of polynomials over a finite field and irreducibility tests
• Cantor-Zassenhaus algorithm

References

• Berlekamp, Elwyn R. (1967). "Factoring Polynomials Over Finite Fields". Bell System Technical Journal. 46: 1853–1859. MR 0219231. BSTJ Later republished in: Berlekamp, Elwyn R. (1968). Algebraic Coding Theory. McGraw Hill. ISBN 0-89412-063-8.
• Knuth, Donald E (1997). "4.6.2 Factorization of Polynomials". Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (Third ed.). Reading, Massachusetts: Addison-Wesley. pp. 439–461, 678–691. ISBN 0-201-89684-2.