mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, 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 Matrix (: matrices or matrixes) or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the m ...

reduction and polynomial GCD computations. It was invented by

Elwyn Berlekamp Elwyn Ralph Berlekamp (September 6, 1940 – April 9, 2019) was a professor of mathematics and computer science at the University of California, Berkeley.Cantor–Zassenhaus algorithm of 1981. It is currently implemented in many well-known

computer algebra system A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The de ...

Overview

Berlekamp's algorithm takes as input a

square-free polynomial In mathematics, a square-free polynomial is a univariate polynomial (over a field or an integral domain) that has no multiple root in an algebraically closed field containing its coefficients. In characteristic 0, or over a finite field, a univar ...

f(x)

(i.e. one with no repeated factors) of degree

n

with coefficients in a finite field

\mathbb_q

and gives as output a polynomial

g(x)

with coefficients in the same field such that

g(x)

divides

f(x)

. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of

f(x)

into powers of

irreducible polynomial In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted f ...

s (recalling that the

ring (The) Ring(s) may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell Arts, entertainment, and media Film and TV * ''The Ring'' (franchise), a ...

of polynomials over a finite field is a

unique factorization domain In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...

). All possible factors of

f(x)

are contained within the

factor ring In ring theory, a branch of abstract algebra, a quotient ring, also known as factor ring, difference ring or residue class ring, is a construction quite similar to the quotient group in group theory and to the quotient space (linear algebra), quo ...

R = \frac.

The algorithm focuses on polynomials

g(x) \in R

which satisfy the congruence: :

g(x)^q \equiv g(x) \pmod.\,

These polynomials form a

subalgebra In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations. "Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear opera ...

of R (which can be considered as an

n

-dimensional vector space over

\mathbb_q

), called the ''Berlekamp subalgebra''. The Berlekamp subalgebra is of interest because the polynomials

g(x)

it contains satisfy :

f(x) = \prod_ \gcd(f(x),g(x)-s).

In general, not every GCD in the above product will be a non-trivial factor of

f(x)

, but some are, providing the factors we seek. Berlekamp's algorithm finds polynomials

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 Kernel may refer to: Computing * Kernel (operating system), the central component of most operating systems * Kernel (image processing), a matrix used for image convolution * Compute kernel, in GPGPU programming * Kernel method, in machine learnin ...

of a certain

n \times n

matrix over

\mathbb_q

, which is derived from the so-called Berlekamp matrix of the polynomial, denoted

\mathcal

. If

\mathcal=_/math> then q_is the coefficient of the j -th power term in the reduction of x^modulo f(x), i.e.:

: x^ \equiv q_x^ + q_x^ + \ldots + q_ \pmod.\, With a certain polynomial g(x) \in R, say:

: g(x) = g_x^+g_x^ + \ldots + g_0,\, we may associate the row vector:

: g = (g_0, g_1, \ldots, g_).\, It is relatively straightforward to see that the row vector g\mathcal corresponds, in the same way, to the reduction of g(x)^q modulo f(x) .  Consequently, a polynomial g(x) \in R is in the Berlekamp subalgebra if and only if g(\mathcal-I)=0 (where I is the n \times n

identity matrix In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere. It has unique properties, for example when the identity matrix represents a geometric transformation, the obje ...

), i.e. if and only if it is in the null space of

\mathcal-I

. By computing the matrix

\mathcal-I

and reducing it to

reduced row echelon form In linear algebra, a matrix is in row echelon form if it can be obtained as the result of Gaussian elimination. Every matrix can be put in row echelon form by applying a sequence of elementary row operations. The term ''echelon'' comes from the ...

and then easily reading off a basis for the null space, we may find a basis for the Berlekamp subalgebra and hence construct polynomials

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 In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of Euclidean division of integers. Th ...

, we may compute these GCDs using the

Euclidean algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is a ...

Conceptual algebraic explanation

With some abstract algebra, the idea behind Berlekamp's algorithm becomes conceptually clear. We represent a finite field

\mathbb_q

, where

q = p^m

for some prime

p

, as

\mathbb_p (g(y))

. We can assume that

f(x) \in \mathbb_q

is square free, by taking all possible pth roots and then computing the gcd with its derivative. Now, suppose that

f(x) = f_1(x) \ldots f_n(x)

is the factorization into irreducibles. Then we have a ring isomorphism,

\sigma: \mathbb_q (f(x)) \to \prod_i \mathbb_q (f_i(x))

, given by the Chinese remainder theorem. The crucial observation is that the Frobenius automorphism

x \to x^p

commutes with

\sigma

, so that if we denote

\text_p(R) = \

, then

\sigma

restricts to an isomorphism

\text_p( \mathbb_q (f(x)) ) \to \prod_^n \text_p( \mathbb_q (f_i(x)) )

. By finite field theory,

\text_p( \mathbb_q (f_i(x)) )

is always the prime subfield of that field extension. Thus,

\text_p( \mathbb_q (f(x)) )

has

p

elements if and only if

f(x)

is irreducible. Moreover, we can use the fact that the Frobenius automorphism is

\mathbb_p

-linear to calculate the fixed set. That is, we note that

\text_p( \mathbb_q (f(x)) )

is a

\mathbb_p

-subspace, and an explicit basis for it can be calculated in the polynomial ring

\mathbb_p,y (f,g)

by computing

(x^i y^j)^p

and establishing the linear equations on the coefficients of

x,y

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

p

we can construct any

(f(x)) ) \setminus \mathbb_p

, and then observe that for some

a \in \mathbb_p

there are

i,j

so that

g - a = 0 \mod f_i

and

g - a \not = 0 \mod f_j

. Such a

g - a

has a nontrivial factor in common with

f(x)

, which can be computed via the gcd. As

p

is small, we can cycle through all possible

a

. * For the case of large primes, which are necessarily odd, one can exploit the fact that a random nonzero element of

\mathbb_p^*

is a square with probability

1/2

, and that the map

x \to x^

maps the set of non-zero squares to

1

, and the set of non-squares to

-1

. Thus, if we take a random element

g \in \text_p( \mathbb_q f(x))

, then with good probability

g^ - 1

will have a non-trivial factor in common with

f(x)

. For further details one can consult.

Applications

One important application of Berlekamp's algorithm is in computing

discrete logarithm In mathematics, for given real numbers a and b, the logarithm \log_b(a) is a number x such that b^x=a. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm \log_b(a) is an integer k such that b^k=a ...

s over finite fields

\mathbb_

, where

p

is prime and

n\geq 2

. Computing discrete logarithms is an important problem in

public key cryptography Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic al ...

and error-control coding. 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

\mathbb_

in the usual way - that is, as polynomials over the base field

\mathbb_

, reduced modulo an irreducible polynomial of degree

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 th
factormod
command, and the

WolframAlpha WolframAlpha ( ) is an answer engine developed by Wolfram Research. It is offered as an online service that answers factual queries by computing answers from externally sourced data. History Launch preparations for WolframAlpha began on Ma ...

br>
website.

References

BSTJ
Later republished in: *{{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 ''The Art of Computer Programming'' (''TAOCP'') is a comprehensive multi-volume monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. it consists of published volumes 1, 2, 3, 4A, and 4 ...

, volume=2 , edition=Third , location=Reading, Massachusetts , publisher=Addison-Wesley , year=1997 , pages=439–461, 678–691 , isbn=0-201-89684-2 Computer algebra Finite fields Polynomial factorization algorithms

Overview

Conceptual algebraic explanation

Applications

Implementation in computer algebra systems

See also

References