Berlekamp–Zassenhaus algorithm: Difference between revisions

Revision as of 14:59, 5 June 2012

Latest revision as of 02:11, 13 May 2024

(15 intermediate revisions by 10 users not shown)

Line 1:

{{format footnotes |date=May 2024}}

In [[mathematics]], in particular in [[computer algebra|computational algebra]], the '''Berlekamp–Zassenhaus algorithm''' is an [[algorithm]] for factoring [[polynomial]]s over the [[integer]]s, named after [[Elwyn Berlekamp]] and [[Hans Zassenhaus]]. As a consequence of [[Gauss's lemma (number theory)|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{{harvtxt|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.

==See also==

*[[Berlekamp's algorithm]]

==References==

*{{citation

* Berlekamp, E. R. "Factoring Polynomials over Finite Fields." Bell System Technical J. 46, 1853–1859, 1967.

| last = Berlekamp | first = E. R. | authorlink = Elwyn Berlekamp

| journal = [[Bell System Technical Journal]]

* Berlekamp, E. R. "Factoring Polynomials over Finite Fields." Math. Comput. 24, 713–735, 1970.

| mr = 0219231

| pages = 1853–1859

* Cantor, D. G. and Zassenhaus, H. "A New Algorithm for Factoring Polynomials over Finite Fields." Math. Comput. 36, 587–592, 1981.

| title = Factoring polynomials over finite fields

| volume = 46

* Geddes, K. O.; Czapor, S. R.; and Labahn, G. Algorithms for Computer Algebra. Amsterdam, Netherlands: Kluwer, 1992.

| year = 1967

| issue = 8 | doi=10.1002/j.1538-7305.1967.tb03174.x}}.

* van Hoeij, M. "Factoring Polynomials and the Knapsack Problem." J. Number Th. 95, 167–189, 2002.

*{{citation

| last = Berlekamp | first = E. R. | authorlink = Elwyn Berlekamp

* Zassenhaus, H. "On Hensel Factorization, I." J. Number Th. 1, 291–311, 1969.

| doi = 10.2307/2004849

| journal = [[Mathematics of Computation]]

| jstor = 2004849

| mr = 0276200

| pages = 713–735

| title = Factoring polynomials over large finite fields

| volume = 24

| year = 1970| issue = 111 | doi-access = free

}}.

*{{citation

| last1 = Cantor | first1 = David G.

| last2 = Zassenhaus | first2 = Hans | author2-link = Hans Zassenhaus

| doi = 10.2307/2007663

| issue = 154

| journal = [[Mathematics of Computation]]

| jstor = 2007663

| mr = 606517

| pages = 587–592

| title = A new algorithm for factoring polynomials over finite fields

| volume = 36

| year = 1981| doi-access = free

}}.

*{{citation

| last1 = Geddes

| first1 = K. O.

| last2 = Czapor

| first2 = S. R.

| last3 = Labahn

| first3 = G.

| doi = 10.1007/b102438

| isbn = 0-7923-9259-0

| ___location = Boston, MA

| mr = 1256483

| publisher = Kluwer Academic Publishers

| title = Algorithms for computer algebra

| year = 1992

| bibcode = 1992afca.book.....G

| url-access = registration

| url = https://archive.org/details/algorithmsforcom0000gedd

}}.

*{{citation

| last = Van Hoeij | first = Mark

| doi = 10.1016/S0022-314X(01)92763-5

| issue = 2

| journal = [[Journal of Number Theory]]

| mr = 1924096

| pages = 167–189

| title = Factoring polynomials and the knapsack problem

| volume = 95

| year = 2002| doi-access = free

}}.

*{{citation

| last = Zassenhaus | first = Hans | authorlink = Hans Zassenhaus

| doi = 10.1016/0022-314X(69)90047-X

| journal = [[Journal of Number Theory]]

| mr = 0242793

| pages = 291–311

| title = On Hensel factorization. I

| volume = 1

| year = 1969| issue = 3 | bibcode = 1969JNT.....1..291Z | doi-access =

}}.

==External links==

*{{mathworld|id=Berlekamp-ZassenhausAlgorithm|title=Berlekamp-Zassenhaus Algorithm|author=Domazet, Haris}}

* Berlekamp–Zassenhaus' algorithm at WolframMathWorld. [http://mathworld.wolfram.com/Berlekamp-ZassenhausAlgorithm.html]

==See also==

*[[Berlekamp's algorithm]]

[[Category:Computer algebra]]