Berlekamp's algorithm

Berlekamp's 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 f(x) (i.e. one with no repeated factors) of degree n with coefficients in a finite field mathbb{F}_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 polynomials (recalling that the ring of polynomials over a finite field is a unique factorization domain).

All possible factors of f(x) are contained within the factor ring:R = frac{mathbb{F}_q [x] }{langle f(x) angle}.The algorithm focuses on polynomials g(x) in R which satisfy the congruence::g(x)^q equiv g(x) pmod{f(x)}.These polynomials form a subalgebra of R (which can be considered as an n-dimensional vector space over mathbb{F}_q), called the "Berlekamp subalgebra". The Berlekamp subalgebra is of interest because the polynomials g(x) it contains satisfy

: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 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 null space of a certain n imes n matrix over mathbb{F}_q, which is derived from the so-called Berlekamp matrix of the polynomial, denoted mathcal{Q}. If mathcal{Q}= [q_{i,j}] then q_{i,j} is the coefficient of the j-th power term in the reduction of x^{iq} modulo f(x), i.e.:

: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 g(x) in R, say:

:g(x) = g_nx^n+g_{n-1}x^{n-1} + ldots + g_0,

we may associate the row vector:

:g = (g_0, g_1, ldots, g_n).

It is relatively straightforward to see that the row vector gmathcal{Q} 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{Q}-I)=0 (where I is the n imes n identity matrix, i.e. if and only if it is in the null space of mathcal{Q}-I.

By computing the matrix 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 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 mathbb{F}_{p^n}, where p is prime and ngeq 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 mathbb{F}_{p^n} in the usual way - that is, as polynomials over the base field mathbb{F}_{p}, 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 the [http://pari.math.u-bordeaux.fr/dochtml/html.stable/Arithmetic_functions.html#factormod factormod] command.

References

* 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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Berlekamp–Massey algorithm — The Berlekamp–Massey algorithm is an algorithm for finding the shortest linear feedback shift register (LFSR) for a given output sequence. Equivalently, it is an algorithm for finding the minimal polynomial of a linearly recurrent sequence.The… …   Wikipedia

  • Elwyn Berlekamp — Infobox Scientist name = Elwyn R Berlekamp |185px image width = 125px birth date = Birth date and age|1940|9|6 death date = residence = USA alma mater = MIT field = Information theory, Coding theory, Combinatorial game theory known for =… …   Wikipedia

  • Cantor–Zassenhaus algorithm — In mathematics, particularly computational algebra, the Cantor–Zassenhaus algorithm is a well known method for factorising polynomials over finite fields (also called Galois fields).The algorithm consists mainly of exponentiation and polynomial… …   Wikipedia

  • Block Wiedemann algorithm — The Block Wiedemann algorithm for computing kernel vectors of a matrix over a finite field is a generalisation of an algorithm due to Don Coppersmith. Coppersmith s algorithm Let M be an n imes n square matrix over some finite field F, let x… …   Wikipedia

  • Elwyn Berlekamp — Elwyn Ralph Berlekamp Naissance 6 septembre 1940 Dover (Ohio) (en …   Wikipédia en Français

  • Reed-Sloane algorithm — The Reed Sloane algorithm is an extension of the Berlekamp Massey algorithm for use on sequences that take their values from the integers mod n …   Wikipedia

  • Reed–Solomon error correction — Reed Solomon error correction is an error correcting code that works by oversampling a polynomial constructed from the data. The polynomial is evaluated at several points, and these values are sent or recorded. Sampling the polynomial more often… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Polynomial — In mathematics, a polynomial (from Greek poly, many and medieval Latin binomium, binomial [1] [2] [3], the word has been introduced, in Latin, by Franciscus Vieta[4]) is an expression of finite length constructed from variables (also known as… …   Wikipedia

  • BCH code — In coding theory the BCH codes form a class of parameterised error correcting codes which have been the subject of much academic attention in the last fifty years. BCH codes were invented in 1959 by Hocquenghem, and independently in 1960 by Bose… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”