In
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 ...
, in particular in
computational algebra, the Berlekamp–Zassenhaus algorithm is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
for factoring
polynomial
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
s over the
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s, named after
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.[Hans Zassenhaus
Hans Julius Zassenhaus (28 May 1912 – 21 November 1991) was a German mathematician, known for work in many parts of abstract algebra, and as a pioneer of computer algebra.
Biography
He was born in Koblenz in 1912.
His father was a historian and ...]
. 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
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
s using
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 univariate polynomial has a simple root modulo a prime number , then this root can be ''lifted'' to ...
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.
improved this algorithm by using the
LLL algorithm LLL may refer to:
Businesses and organisations
* L3 Technologies, an American defense contractor formerly with the NYSE stock symbol LLL
* La Leche League, an organization that promotes breastfeeding
Education
* LL.L (''Legum Licentiatus''), a ...
, substantially reducing the time needed to choose the right subsets of mod ''p'' factors.
See also
*
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 ...
References
*.
*.
*.
*.
*.
*.
External links
*
Computer algebra
{{Algorithm-stub