Berlekamp–Zassenhaus algorithm: Difference between revisions

Revision as of 12:46, 26 November 2015

Latest revision as of 02:11, 13 May 2024

(8 intermediate revisions by 6 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.

Line 5 ⟶ 6:

{{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==

Line 13 ⟶ 17:

| pages = 1853–1859

| title = Factoring polynomials over finite fields

| url = http://www.alcatel.hu/bstj/vol46-1967/articles/bstj46-8-1853.pdf

| volume = 46

| year = 1967

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

*{{citation

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

Line 26 ⟶ 29:

| title = Factoring polynomials over large finite fields

| volume = 24

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

}}.

*{{citation

| last1 = Cantor | first1 = David G.

Line 38 ⟶ 42:

| 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

Line 49 ⟶ 57:

| 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

Line 59 ⟶ 71:

| title = Factoring polynomials and the knapsack problem

| volume = 95

| year = 2002}}.| doi-access = free

}}.

*{{citation

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

Line 68 ⟶ 81:

| 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}}

==See also==

*[[Berlekamp's algorithm]]

{{DEFAULTSORT:Berlekamp-Zassenhaus algorithm}}

[[Category:Computer algebra]]