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 with elements. 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]
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]
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]
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]
Due to Euler's criterion, for every monomial exactly one of following properties holds: [1]
Thus if is not divisible by , which may be checked separately, then is equal to the product of greatest common divisors and . [7]
The property above leads to the following algorithm: [1]
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 .
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:
In the third case GCD is equal to either or . It allows to write the solution as . [1]
Assume we need to solve the equation . For this we need to factorize . Consider some possible values of :
A manual check shows that, indeed, and .
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 .
Let a polynomial have degree . We derive the algorithm's complexity as follows:
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]
{{
cite book}}
: CS1 maint: multiple names: authors list (
link)
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 with elements. 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]
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]
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]
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]
Due to Euler's criterion, for every monomial exactly one of following properties holds: [1]
Thus if is not divisible by , which may be checked separately, then is equal to the product of greatest common divisors and . [7]
The property above leads to the following algorithm: [1]
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 .
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:
In the third case GCD is equal to either or . It allows to write the solution as . [1]
Assume we need to solve the equation . For this we need to factorize . Consider some possible values of :
A manual check shows that, indeed, and .
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 .
Let a polynomial have degree . We derive the algorithm's complexity as follows:
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]
{{
cite book}}
: CS1 maint: multiple names: authors list (
link)