# Berlekamp–Rabin algorithm

In number theory, **Berlekamp's root finding algorithm**, also called the **Berlekamp–Rabin algorithm**, is the probabilistic method of finding roots of polynomials over a field . The method was discovered by Elwyn Berlekamp in 1970^{[1]} as an auxiliary to the algorithm for polynomial factorization over finite fields. The algorithm was later modified by Rabin for arbitrary finite fields in 1979.^{[2]} The method was also independently discovered before Berlekamp by other researchers.^{[3]}

## History[edit]

The method was proposed by Elwyn Berlekamp in his 1970 work^{[1]} on polynomial factorization over finite fields. His original work lacked a formal correctness proof^{[2]} and was later refined and modified for arbitrary finite fields by Michael Rabin.^{[2]} In 1986 René Peralta proposed a similar algorithm^{[4]} for finding square roots in .^{[5]} In 2000 Peralta's method was generalized for cubic equations.^{[6]}

## Statement of problem[edit]

Let be an odd prime number. Consider the polynomial over the field of remainders modulo . The algorithm should find all in such that in .^{[2]}^{[7]}

## Algorithm[edit]

### Randomization[edit]

Let . Finding all roots of this polynomial is equivalent to finding its factorization into linear factors. To find such factorization it is sufficient to split the polynomial into any two non-trivial divisors and factorize them recursively. To do this, consider the polynomial where is some any element of . If one can represent this polynomial as the product then in terms of the initial polynomial it means that , which provides needed factorization of .^{[1]}^{[7]}

### Classification of elements[edit]

Due to Euler's criterion, for every monomial exactly one of following properties holds:^{[1]}

- The monomial is equal to if ,
- The monomial divides if is quadratic residue modulo ,
- The monomial divides if is quadratic non-residual modulo .

Thus if is not divisible by , which may be checked separately, then is equal to the product of greatest common divisors and .^{[7]}

### Berlekamp's method[edit]

The property above leads to the following algorithm:^{[1]}

- Explicitly calculate coefficients of ,
- Calculate remainders of modulo by squaring the current polynomial and taking remainder modulo ,
- Using exponentiation by squaring and polynomials calculated on the previous steps calculate the remainder of modulo ,
- If then mentioned above provide a non-trivial factorization of ,
- Otherwise all roots of are either residues or non-residues simultaneously and one has to choose another .

If is divisible by some non-linear primitive polynomial over then when calculating with and one will obtain a non-trivial factorization of , thus algorithm allows to find all roots of arbitrary polynomials over .

### Modular square root[edit]

Consider equation having elements and as its roots. Solution of this equation is equivalent to factorization of polynomial over . In this particular case problem it is sufficient to calculate only . For this polynomial exactly one of the following properties will hold:

- GCD is equal to which means that and are both quadratic non-residues,
- GCD is equal to which means that both numbers are quadratic residues,
- GCD is equal to which means that exactly one of these numbers is quadratic residue.

In the third case GCD is equal to either or . It allows to write the solution as .^{[1]}

### Example[edit]

Assume we need to solve the equation . For this we need to factorize . Consider some possible values of :

- Let . Then , thus . Both numbers are quadratic non-residues, so we need to take some other .

- Let . Then , thus . From this follows , so and .

A manual check shows that, indeed, and .

## Correctness proof[edit]

The algorithm finds factorization of in all cases except for ones when all numbers are quadratic residues or non-residues simultaneously. According to theory of cyclotomy,^{[8]} the probability of such an event for the case when are all residues or non-residues simultaneously (that is, when would fail) may be estimated as where is the number of distinct values in .^{[1]} In this way even for the worst case of and , the probability of error may be estimated as and for modular square root case error probability is at most .

## Complexity[edit]

Let a polynomial have degree . We derive the algorithm's complexity as follows:

- Due to the binomial theorem , we may transition from to in time.
- Polynomial multiplication and taking remainder of one polynomial modulo another one may be done in , thus calculation of is done in .
- Binary exponentiation works in .
- Taking the of two polynomials via Euclidean algorithm works in .

Thus the whole procedure may be done in . Using the fast Fourier transform and Half-GCD algorithm,^{[9]} the algorithm's complexity may be improved to . For the modular square root case, the degree is , thus the whole complexity of algorithm in such case is bounded by per iteration.^{[7]}

## References[edit]

- ^
^{a}^{b}^{c}^{d}^{e}^{f}^{g}Berlekamp, E. R. (1970). "Factoring polynomials over large finite fields".*Mathematics of Computation*.**24**(111): 713–735. doi:10.1090/S0025-5718-1970-0276200-X. ISSN 0025-5718. - ^
^{a}^{b}^{c}^{d}M. Rabin (1980). "Probabilistic Algorithms in Finite Fields".*SIAM Journal on Computing*.**9**(2): 273–280. doi:10.1137/0209024. ISSN 0097-5397. **^**Donald E Knuth (1998).*The art of computer programming. Vol. 2 Vol. 2*. ISBN 978-0201896848. OCLC 900627019.**^**Tsz-Wo Sze (2011). "On taking square roots without quadratic nonresidues over finite fields".*Mathematics of Computation*.**80**(275): 1797–1811. arXiv:0812.2591. doi:10.1090/s0025-5718-2011-02419-1. ISSN 0025-5718. S2CID 10249895.**^**R. Peralta (November 1986). "A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)".*IEEE Transactions on Information Theory*.**32**(6): 846–847. doi:10.1109/TIT.1986.1057236. ISSN 0018-9448.**^**C Padró, G Sáez (August 2002). "Taking cube roots in Zm".*Applied Mathematics Letters*.**15**(6): 703–708. doi:10.1016/s0893-9659(02)00031-9. ISSN 0893-9659.- ^
^{a}^{b}^{c}^{d}Alfred J. Menezes, Ian F. Blake, XuHong Gao, Ronald C. Mullin, Scott A. Vanstone (1993).*Applications of Finite Fields*. The Springer International Series in Engineering and Computer Science. Springer US. ISBN 9780792392828.CS1 maint: multiple names: authors list (link) **^**Marshall Hall (1998).*Combinatorial Theory*. John Wiley & Sons. ISBN 9780471315186.**^**Aho, Alfred V. (1974).*The design and analysis of computer algorithms*. Addison-Wesley Pub. Co. ISBN 0201000296.