Berlekamp–Zassenhaus algorithm
Encyclopedia
In mathematics
, in particular in computational algebra, the Berlekamp–Zassenhaus algorithm is an algorithm
for factoring polynomial
s over the integer
s. As a consequence of Gauss's lemma
, this amounts to solving the problem also over the rationals. The algorithm starts by finding factorizations over suitable finite field
s using Hensel's lemma
to lift the solution from modulo a prime p to a convenient power of p. After this the right factors are found as a subset of these. The worst case of this algorithm is exponential in the number of factors.
van Hoeij (2002) improved this algorithm by using the LLL algorithm, substantially reducing the time needed to choose the right subsets of mod p factors.
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...
, in particular in computational algebra, the Berlekamp–Zassenhaus algorithm is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for factoring polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
s over the integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s. As a consequence of Gauss's lemma
Gauss's lemma (number theory)
Gauss's lemma in number theory gives a condition for an integer to be a quadratic residue. Although it is not useful computationally, it has theoretical significance, being involved in some proofs of quadratic reciprocity....
, this amounts to solving the problem also over the rationals. The algorithm starts by finding factorizations over suitable 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 using Hensel's lemma
Hensel's lemma
In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a polynomial equation has a simple root modulo a prime number , then this root corresponds to a unique root of the same equation modulo any higher power...
to lift the solution from modulo a prime p to a convenient power of p. After this the right factors are found as a subset of these. The worst case of this algorithm is exponential in the number of factors.
van Hoeij (2002) improved this algorithm by using the LLL algorithm, substantially reducing the time needed to choose the right subsets of mod p factors.
External links
- Berlekamp–Zassenhaus' algorithm at WolframMathWorld. http://mathworld.wolfram.com/Berlekamp-ZassenhausAlgorithm.html