Berlekamp–Rabin algorithm explained

F _{p} with p 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]

History

The method was proposed by Elwyn Berlekamp in his 1970 work on polynomial factorization over finite fields. His original work lacked a formal correctness proof and was later refined and modified for arbitrary finite fields by Michael Rabin. In 1986 René Peralta proposed a similar algorithm^[4] for finding square roots in

F _{p} .^[5] In 2000 Peralta's method was generalized for cubic equations.^[6]

Statement of problem

Let

p be an odd prime number. Consider the polynomial $f(x)\; =\; a\_0\; +\; a\_1\; x\; +\; \backslash cdots\; +\; a\_n\; x^n$ over the field F _{p\simeq} Z/p Z of remainders modulo p . The algorithm should find all λ in F _{p} such that $f(\backslash lambda)=\; 0$ in F _{p} .^[7]

Algorithm

Randomization

Let $f(x)\; =\; (x-\backslash lambda\_1)(x-\backslash lambda\_2)\backslash cdots(x-\backslash 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-\backslash lambda\_1\; -\; z)(x-\backslash lambda\_2\; -\; z)\; \backslash cdots\; (x-\backslash lambda\_n-z)$ where

z  is some element of 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) .

Classification of

F _{p} elements (x -λ ) exactly one of following properties holds:

1. The monomial is equal to

x if λ = 0 ,

1. The monomial divides $g\_0(x)=(x^-1)$ if

λ  is quadratic residue modulo p ,

1. The monomial divides $g\_1(x)=(x^+1)$ if

λ  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))} .

Berlekamp's method

The property above leads to the following algorithm:

1. Explicitly calculate coefficients of

f _{z(x)} = f(x - z) ,

1. Calculate remainders of $x,x^2,\; x^,x^,\; x^,\; \backslash ldots,\; x^$ modulo

f _{z(x)} by squaring the current polynomial and taking remainder modulo f _{z(x)} ,

1. Using exponentiation by squaring and polynomials calculated on the previous steps calculate the remainder of $x^$ modulo $f\_z(x)$,
2. If $x^\; \backslash not\; \backslash equiv\; \backslash pm\; 1\; \backslash pmod$ then

\gcd mentioned below provide a non-trivial factorization of f _{z(x)} ,

1. 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 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 F _{p} .

Modular square root

Consider equation $x^2\; \backslash equiv\; a\; \backslash pmod$ having elements

\beta and - \beta as its roots. Solution of this equation is equivalent to factorization of polynomial $f(x)\; =\; x^2-a=(x-\backslash beta)(x+\backslash beta)$ over 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:

1. GCD is equal to

1 which means that z + \beta and z - \beta are both quadratic non-residues,

1. GCD is equal to

f _{z(x)} which means that both numbers are quadratic residues,

1. 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 $\backslash beta\; =\; (t\; -\; z)\; \backslash pmod$.

Example

Assume we need to solve the equation $x^2\; \backslash equiv\; 5\backslash pmod$. For this we need to factorize

f(x) = x ^{2-5=(x-\beta)(x+\beta)} . Consider some possible values of z :

1. Let

z =3 . Then f _{z(x)} = (x -3 ) ^{2} - 5 = x ^{2} - 6 x + 4 , thus \gcd(x ^{2} - 6 x + 4 ; x ^{5} - 1 ) = 1 . Both numbers 3 \pm \beta are quadratic non-residues, so we need to take some other z .

1. Let

z =2 . Then f _{z(x)} = (x -2 ) ^{2} - 5 = x ^{2} - 4 x - 1 , thus $\backslash gcd(x^2\; -\; 4x\; -\; 1\; ;\; x^5\; -\; 1)\backslash equiv\; x\; -\; 9\; \backslash pmod$. From this follows $x\; -\; 9\; =\; x\; -\; 2\; -\; \backslash beta$, so \beta \equiv 7 \pmod{ 11 } and $-\backslash beta\; \backslash equiv\; -7\; \backslash equiv\; 4\; \backslash pmod$.

A manual check shows that, indeed, $7^2\; \backslash equiv\; 49\; \backslash equiv\; 5\backslash pmod$ and $4^2\backslash equiv\; 16\; \backslash equiv\; 5\backslash pmod$.

Correctness proof

The algorithm finds factorization of

f _{z(x)} in all cases except for ones when all numbers z +λ _{1,} z +λ _{2,} \ldots, z +λ _{n} are quadratic residues or non-residues simultaneously. According to theory of cyclotomy,^[8] the probability of such an event for the case when λ _{1,} \ldots, λ _{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 λ _{1,} \ldots, λ _{n} . In this way even for the worst case of k =1 and f(x) = (x -λ ) ^{n} , the probability of error may be estimated as 1 / 2 and for modular square root case error probability is at most 1 / 4 .

Complexity

Let a polynomial have degree

n . We derive the algorithm's complexity as follows:

1. Due to the binomial theorem $(x-z)^k\; =\; \backslash sum\backslash limits\_^k\; \backslash binom\; (-z)^x^i$, we may transition from

f(x) to f(x - z) in O(n ^{2)} time.

1. Polynomial multiplication and taking remainder of one polynomial modulo another one may be done in $O(n^2)$, thus calculation of $x^\; \backslash bmod\; f\_z(x)$ is done in $O(n^2\; \backslash log\; p)$.
2. Binary exponentiation works in

O(n ^{2} log p) .

1. 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,^[9] 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.

Notes and References

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