Content deleted Content added
|
|
|
In [[number theory]], the '''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 |author = |editor= |format= |url= https://www.ams.org/mcom/1970-24-111/S0025-5718-1970-0276200-X/ |title= Factoring polynomials over large finite fields |type= |origyear= | agency = |edition= Mathematics of Computation |___location= |year= 1970 |publisher= |at= |volume= 24 |issue= 111 |number= |pages = 713–735 |page= |series= |isbn = |issn = 00255718 |doi = 10.1090/S0025-5718-1970-0276200-X |bibcode = |arxiv = |pmid = |ref= |archiveurl = |archivedate = |language= en |quote= }}</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 |editor= |format= |url= https://epubs.siam.org/doi/10.1137/0209024 |title= Probabilistic Algorithms in Finite Fields |type= |origyear= | agency = |edition= SIAM Journal on Computing |___location= |year= 1980 |publisher= |at= |volume= 9 |issue= 2 |number= |pages = 273–280 |page= |series= |isbn = |issn = 00975397 |doi = 10.1137/0209024 |bibcode = |arxiv = |pmid = |ref= |archiveurl = |archivedate = |language= |quote= }}</ref> The method was also independently discovered before Berlekamp by other researchers.<ref>{{cite book| author = Donald E Knuth | chapter = | chapter-url = | format = | url = https://www.worldcat.org/title/art-of-computer-programming-vol-2/oclc/900627019&referer=brief_results | title = The art of computer programming. Vol. 2 Vol. 2 | orig-year = | agency = | edition = |___location= |date = 1998 |publisher= |at= |volume= |issue = | pages = | page = | series = | isbn = 9780201896848| ref = }}</ref>
== History ==
|
