Content deleted Content added
m Open access bot: doi updated in citation with #oabot. |
Added free to read link in citations with OAbot #oabot |
||
Line 1:
{{short description|Method in number theory}}
In [[number theory]], '''Berlekamp's root finding algorithm''', also called the '''Berlekamp–Rabin algorithm''', is the [[Randomized algorithm|probabilistic]] method of [[Root-finding algorithm|finding roots]] of [[Polynomial|polynomials]] over a [[Finite field|field]] <math>\mathbb Z_p</math>. The method was discovered by [[Elwyn Berlekamp]] in 1970<ref name=":0">{{cite journal |url= https://www.ams.org/mcom/1970-24-111/S0025-5718-1970-0276200-X/ |title= Factoring polynomials over large finite fields |journal= Mathematics of Computation |year= 1970 |volume= 24 |issue= 111 |pages = 713–735 |issn = 0025-5718 |doi = 10.1090/S0025-5718-1970-0276200-X |language= en |last1= Berlekamp|first1= E. R.|doi-access= free}}</ref> as an auxiliary to the [[Berlekamp's algorithm|algorithm]] for polynomial factorization over finite fields. The algorithm was later modified by [[Michael O. Rabin|Rabin]] for arbitrary finite fields in 1979.<ref name=":1">{{cite journal |author = M. Rabin |title= Probabilistic Algorithms in Finite Fields |journal= SIAM Journal on Computing |year= 1980 |volume= 9 |issue= 2 |pages = 273–280 |issn = 0097-5397 |doi = 10.1137/0209024 |citeseerx= 10.1.1.17.5653 }}</ref> The method was also independently discovered before Berlekamp by other researchers.<ref>{{cite book| author = Donald E Knuth | author-link = Donald E Knuth | title = The art of computer programming. Vol. 2 Vol. 2 |date = 1998 | isbn = 978-0201896848| oclc = 900627019 }}</ref>
== History ==
| |||