Berlekamp–Rabin algorithm
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In number theory, Berlekamp's root finding algorithm, also called the Berlekamp–Rabin algorithm, is the probabilistic method of finding roots of polynomials over the field \mathbb F_p with p elements. The method was discovered by Elwyn Berlekamp in 1970 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. The method was also independently discovered before Berlekamp by other researchers.
In number theory, Berlekamp's root finding algorithm, also called the Berlekamp–Rabin algorithm, is the probabilistic method of finding roots of polynomials over the field \mathbb F_p with p elements. The method was discovered by Elwyn Berlekamp in 1970 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. The method was also independently discovered before Berlekamp by other researchers.
Statement of problem
Let p be an odd prime number. Consider the polynomial f(x) = a_0 + a_1 x + \cdots + a_n x^n over the field \mathbb F_p\simeq \mathbb Z/p\mathbb Z of remainders modulo p . The algorithm should find all \lambda in \mathbb F_p such that f(\lambda)= 0 in \mathbb F_p . Let f(x) = (x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_n) . 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 f_z(x)=f(x-z) = (x-\lambda_1 - z)(x-\lambda_2 - z) \cdots (x-\lambda_n-z) where z is some element of \mathbb F_p . If one can represent this polynomial as the product f_z(x)=p_0(x)p_1(x) then in terms of the initial polynomial it means that f(x) =p_0(x+z)p_1(x+z) , which provides needed factorization of f(x) .
The monomial is equal to x if \lambda = 0 , The monomial divides g_0(x)=(x^{(p-1)/2}-1) if \lambda is quadratic residue modulo p , The monomial divides g_1(x)=(x^{(p-1)/2}+1) if \lambda is quadratic non-residual modulo p . Thus if f_z(x) is not divisible by x , which may be checked separately, then f_z(x) is equal to the product of greatest common divisors \gcd(f_z(x);g_0(x)) and \gcd(f_z(x);g_1(x)) .
Explicitly calculate coefficients of f_z(x) = f(x-z) , Calculate remainders of x,x^2, x^{2^2},x^{2^3}, x^{2^4}, \ldots, x^{2^{\lfloor \log_2 p \rfloor}} modulo f_z(x) by squaring the current polynomial and taking remainder modulo f_z(x) , Using exponentiation by squaring and polynomials calculated on the previous steps calculate the remainder of x^{(p-1)/2} modulo f_z(x) , If x^{(p-1)/2} \not \equiv \pm 1 \pmod{f_z(x)} then \gcd mentioned below provide a non-trivial factorization of f_z(x) , Otherwise all roots of f_z(x) are either residues or non-residues simultaneously and one has to choose another z .
If f(x) is divisible by some non-linear primitive polynomial g(x) over \mathbb F_p then when calculating \gcd with g_0(x) and g_1(x) one will obtain a non-trivial factorization of f_z(x)/g_z(x) , thus algorithm allows to find all roots of arbitrary polynomials over \mathbb F_p . Consider equation x^2 \equiv a \pmod{p} having elements \beta and -\beta as its roots. Solution of this equation is equivalent to factorization of polynomial f(x) = x^2-a=(x-\beta)(x+\beta) over \mathbb F_p .
In this particular case problem it is sufficient to calculate only \gcd(f_z(x); g_0(x)) . For this polynomial exactly one of the following properties will hold: GCD is equal to 1 which means that z+\beta and z-\beta are both quadratic non-residues, GCD is equal to f_z(x) which means that both numbers are quadratic residues, GCD is equal to (x-t) which means that exactly one of these numbers is quadratic residue. In the third case GCD is equal to either (x-z-\beta) or (x-z+\beta) . It allows to write the solution as \beta = (t - z) \pmod{p} .
Assume we need to solve the equation x^2 \equiv 5\pmod{11} . For this we need to factorize f(x)=x^2-5=(x-\beta)(x+\beta) . Consider some possible values of z : Let z=3 . Then f_z(x) = (x-3)^2 - 5 = x^2 - 6x + 4 , thus \gcd(x^2 - 6x + 4 ; x^5 - 1) = 1 . Both numbers 3 \pm \beta are quadratic non-residues, so we need to take some other z . Let z=2 . Then f_z(x) = (x-2)^2 - 5 = x^2 - 4x - 1 , thus \gcd( x^2 - 4x - 1 ; x^5 - 1)\equiv x - 9 \pmod{11} .
From this follows x - 9 = x - 2 - \beta , so \beta \equiv 7 \pmod{11} and -\beta \equiv -7 \equiv 4 \pmod{11} . A manual check shows that, indeed, 7^2 \equiv 49 \equiv 5\pmod{11} and 4^2\equiv 16 \equiv 5\pmod{11} . The algorithm finds factorization of f_z(x) in all cases except for ones when all numbers z+\lambda_1, z+\lambda_2, \ldots, z+\lambda_n are quadratic residues or non-residues simultaneously.
According to theory of cyclotomy, the probability of such an event for the case when \lambda_1, \ldots, \lambda_n are all residues or non-residues simultaneously (that is, when z=0 would fail) may be estimated as 2^{-k} where k is the number of distinct values in \lambda_1, \ldots, \lambda_n . In this way even for the worst case of k=1 and f(x)=(x-\lambda)^n , the probability of error may be estimated as 1/2 and for modular square root case error probability is at most 1/4 .
Due to the binomial theorem (x-z)^k = \sum\limits_{i=0}^k \binom{k}{i} (-z)^{k-i}x^i , we may transition from f(x) to f(x-z) in O(n^2) time. Polynomial multiplication and taking remainder of one polynomial modulo another one may be done in O(n^2) , thus calculation of x^{2^k} \bmod f_z(x) is done in O(n^2 \log p) . Binary exponentiation works in O(n^2 \log p) . Taking the \gcd of two polynomials via Euclidean algorithm works in O(n^2) . Thus the whole procedure may be done in O(n^2 \log p) .
Using the fast Fourier transform and Half-GCD algorithm, the algorithm's complexity may be improved to O(n \log n \log pn) . For the modular square root case, the degree is n = 2 , thus the whole complexity of algorithm in such case is bounded by O(\log p) per iteration.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1296403975 under CC BY-SA 4.0; modifications have been made.