Berlekamp-Rabin Algorithm

The Berlekamp-Rabin algorithm is a probabilistic method in number theory for finding the roots of a polynomial over a finite field: given an odd prime p and a polynomial over the field with p elements, it determines every value where the polynomial evaluates to zero. The method was discovered by Elwyn Berlekamp in 1970 as a tool for polynomial factorization over finite fields, though his original presentation lacked a formal correctness proof; Michael O. Rabin refined and generalized it in 1979 to work over arbitrary finite fields, and the algorithm carries both names as a result, though it was also independently discovered by other researchers before Berlekamp's publication. Its central idea is to reduce root-finding to polynomial factorization, recursively splitting a polynomial into smaller non-trivial factors using randomized choices and properties of quadratic residues in the field. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/