Berlekamp's algorithm
Encyclopedia
In mathematics
, particularly computational algebra, Berlekamp's algorithm is a well-known method for factoring polynomials
over finite field
s (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 system
s, including PARI/GP
.
(i.e. one with no repeated factors) of degree 
with coefficients in a finite field 
and gives as output a polynomial 
with coefficients in the same field such that 
divides 
. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of 
into powers of irreducible polynomial
s (recalling that the ring
of polynomials over a finite field is a unique factorization domain
).
All possible factors of
are contained within the factor ring
The algorithm focuses on polynomials
which satisfy the congruence:
These polynomials form a subalgebra of R (which can be considered as an
-dimensional vector space over 
), called the Berlekamp subalgebra. The Berlekamp subalgebra is of interest because the polynomials 
it contains satisfy
In general, not every GCD in the above product will be a non-trivial factor of
, but some are, providing the factors we seek.
Berlekamp's algorithm finds polynomials
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 null space
of a certain
matrix over 
, which is derived from the so-called Berlekamp matrix of the polynomial, denoted 
. If 
then 
is the coefficient of the 
-th power term in the reduction of 
modulo 
, i.e.:
With a certain polynomial
, say:
we may associate the row vector:
It is relatively straightforward to see that the row vector
corresponds, in the same way, to the reduction of 
modulo 
. Consequently a polynomial 
is in the Berlekamp subalgebra if and only if 
(where 
is the 
identity matrix
, i.e. if and only if it is in the null space of
.
By computing the matrix
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 
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
.
s over finite fields
, where 
is prime and 
. 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 
in the usual way - that is, as polynomials over the base field 
, reduced modulo an irreducible polynomial of degree 
- then this is simply polynomial factorisation, as provided by Berlekamp's algorithm.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, particularly computational algebra, Berlekamp's algorithm is a well-known method for factoring polynomials
Polynomial factorization
In mathematics and computer algebra, polynomial factorization refers to factoring a polynomial into irreducible polynomials over a given field.-Formulation of the question:...
over finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
s (also known as Galois fields). The algorithm consists mainly of matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
reduction and polynomial GCD
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
computations. It was invented by Elwyn Berlekamp
Elwyn Berlekamp
Elwyn Ralph Berlekamp is an American mathematician. He is a professor emeritus of mathematics and EECS at the University of California, Berkeley. Berlekamp is known for his work in information theory and combinatorial game theory....
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 system
Computer algebra system
A computer algebra system is a software program that facilitates symbolic mathematics. The core functionality of a CAS is manipulation of mathematical expressions in symbolic form.-Symbolic manipulations:...
s, including PARI/GP
PARI/GP
PARI/GP is a computer algebra system with the main aim of facilitating number theory computations. It is free software; versions 2.1.0 and higher are distributed under the GNU General Public License...
.
Overview
Berlekamp's algorithm takes as input a square-free polynomial (i.e. one with no repeated factors) of degree with coefficients in a finite field and gives as output a polynomial with coefficients in the same field such that divides . The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of into powers of irreducible polynomialIrreducible polynomial
In mathematics, the adjective irreducible means that an object cannot be expressed as the product of two or more non-trivial factors in a given set. See also factorization....
s (recalling that the ring
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
of polynomials over a finite field is a unique factorization domain
Unique factorization domain
In mathematics, a unique factorization domain is, roughly speaking, a commutative ring in which every element, with special exceptions, can be uniquely written as a product of prime elements , analogous to the fundamental theorem of arithmetic for the integers...
).
All possible factors of
are contained within the factor ringThe algorithm focuses on polynomials
which satisfy the congruence:These polynomials form a subalgebra of R (which can be considered as an
-dimensional vector space over ), called the Berlekamp subalgebra. The Berlekamp subalgebra is of interest because the polynomials it contains satisfyIn general, not every GCD in the above product will be a non-trivial factor of
, but some are, providing the factors we seek.Berlekamp's algorithm finds polynomials
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 null spaceNull space
In linear algebra, the kernel or null space of a matrix A is the set of all vectors x for which Ax = 0. The kernel of a matrix with n columns is a linear subspace of n-dimensional Euclidean space...
of a certain
matrix over , which is derived from the so-called Berlekamp matrix of the polynomial, denoted . If then is the coefficient of the -th power term in the reduction of modulo , i.e.:With a certain polynomial
, say:we may associate the row vector:
It is relatively straightforward to see that the row vector
corresponds, in the same way, to the reduction of modulo . Consequently a polynomial is in the Berlekamp subalgebra if and only if (where is the identity matrixIdentity matrix
In linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...
, i.e. if and only if it is in the null space of
.By computing the matrix
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 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 domainEuclidean domain
In mathematics, more specifically in abstract algebra and ring theory, a Euclidean domain is a ring that can be endowed with a certain structure – namely a Euclidean function, to be described in detail below – which allows a suitable generalization of the Euclidean algorithm...
, we may compute these GCDs using the Euclidean algorithm
Euclidean algorithm
In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
.
Applications
One important application of Berlekamp's algorithm is in computing discrete logarithmDiscrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
s over finite fields
, where is prime and . 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 in the usual way - that is, as polynomials over the base field , reduced modulo an irreducible polynomial of degree - then this is simply polynomial factorisation, as provided by Berlekamp's algorithm.