:Berlekamp–Rabin algorithm

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{{cite journal |author = Tsz-Wo Sze |title= On taking square roots without quadratic nonresidues over finite fields |journal= Mathematics of Computation|year= 2011 |volume= 80 |issue= 275 |pages = 1797–1811 |issn = 0025-5718 |doi = 10.1090/s0025-5718-2011-02419-1 |arxiv =0812.2591 |s2cid= 10249895 }} for finding square roots in $\backslash mathbb\; F\_p$.{{cite journal |author = R. Peralta |title= A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.) |journal= IEEE Transactions on Information Theory |date=November 1986 |volume= 32 |issue= 6 |pages = 846–847 |issn = 0018-9448 |doi = 10.1109/TIT.1986.1057236 }} In 2000 Peralta's method was generalized for cubic equations.{{cite journal |author = C Padró, G Sáez |title= Taking cube roots in Zm |journal= Applied Mathematics Letters |date=August 2002 |volume= 15 |issue= 6 |pages = 703–708 |issn = 0893-9659 |doi = 10.1016/s0893-9659(02)00031-9 |doi-access= }}

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 $\backslash mathbb\; F\_p\backslash simeq\; \backslash mathbb\; Z/p\backslash mathbb\; Z$ of remainders modulo $p$. The algorithm should find all $\backslash lambda$ in $\backslash mathbb\; F\_p$ such that $f(\backslash lambda)=\; 0$ in $\backslash mathbb\; F\_p$.{{cite book| author = Alfred J. Menezes, Ian F. Blake, XuHong Gao, Ronald C. Mullin, Scott A. Vanstone | url = https://www.springer.com/gp/book/9780792392828 | title = Applications of Finite Fields |date = 1993 |publisher= Springer US | series = The Springer International Series in Engineering and Computer Science | isbn = 9780792392828}}

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 $\backslash 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)$.

Due to Euler's criterion, for every monomial $(x-\backslash lambda)$ exactly one of following properties holds:

1. The monomial is equal to $x$ if $\backslash lambda\; =\; 0$,
2. The monomial divides $g\_0(x)=(x^\{(p-1)/2\}-1)$ if $\backslash lambda$ is quadratic residue modulo $p$,
3. The monomial divides $g\_1(x)=(x^\{(p-1)/2\}+1)$ if $\backslash 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 $\backslash gcd(f\_z(x);g\_0(x))$ and $\backslash gcd(f\_z(x);g\_1(x))$.

The property above leads to the following algorithm:

1. Explicitly calculate coefficients of $f\_z(x)\; =\; f(x-z)$,
2. Calculate remainders of $x,x^2,\; x^\{2^2\},x^\{2^3\},\; x^\{2^4\},\; \backslash ldots,\; x^\{2^\{\backslash lfloor\; \backslash log\_2\; p\; \backslash rfloor\}\}$ modulo $f\_z(x)$ by squaring the current polynomial and taking remainder modulo $f\_z(x)$,
3. Using exponentiation by squaring and polynomials calculated on the previous steps calculate the remainder of $x^\{(p-1)/2\}$ modulo $f\_z(x)$,
4. If $x^\{(p-1)/2\}\; \backslash not\; \backslash equiv\; \backslash pm\; 1\; \backslash pmod\{f\_z(x)\}$ then $\backslash gcd$ mentioned below provide a non-trivial factorization of $f\_z(x)$,
5. 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 $\backslash mathbb\; F\_p$ then when calculating $\backslash 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 $\backslash mathbb\; F\_p$.

Consider equation $x^2\; \backslash equiv\; a\; \backslash pmod\{p\}$ having elements $\backslash beta$ and $-\backslash 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 $\backslash mathbb\; F\_p$. In this particular case problem it is sufficient to calculate only $\backslash 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+\backslash beta$ and $z-\backslash beta$ are both quadratic non-residues,
2. GCD is equal to $f\_z(x)$which means that both numbers are quadratic residues,
3. 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-\backslash beta)$ or $(x-z+\backslash beta)$. It allows to write the solution as $\backslash beta\; =\; (t\; -\; z)\; \backslash pmod\{p\}$.

Assume we need to solve the equation $x^2\; \backslash equiv\; 5\backslash pmod\{11\}$. For this we need to factorize $f(x)=x^2-5=(x-\backslash beta)(x+\backslash beta)$. Consider some possible values of $z$:

1. Let $z=3$. Then $f\_z(x)\; =\; (x-3)^2\; -\; 5\; =\; x^2\; -\; 6x\; +\; 4$, thus $\backslash gcd(x^2\; -\; 6x\; +\; 4\; ;\; x^5\; -\; 1)\; =\; 1$. Both numbers $3\; \backslash pm\; \backslash 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\; -\; 4x\; -\; 1$, thus $\backslash gcd(\; x^2\; -\; 4x\; -\; 1\; ;\; x^5\; -\; 1)\backslash equiv\; x\; -\; 9\; \backslash pmod\{11\}$. From this follows $x\; -\; 9\; =\; x\; -\; 2\; -\; \backslash beta$, so $\backslash beta\; \backslash equiv\; 7\; \backslash pmod\{11\}$ and $-\backslash beta\; \backslash equiv\; -7\; \backslash equiv\; 4\; \backslash pmod\{11\}$.

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

The algorithm finds factorization of $f\_z(x)$ in all cases except for ones when all numbers $z+\backslash lambda\_1,\; z+\backslash lambda\_2,\; \backslash ldots,\; z+\backslash lambda\_n$ are quadratic residues or non-residues simultaneously. According to theory of cyclotomy,{{cite book| author = Marshall Hall | url = https://books.google.com/books?id=__JCiiCfu2EC&q=Combinatorial+Theory+hall&pg=PA1 | title = Combinatorial Theory |date = 1998 |publisher= John Wiley & Sons | isbn = 9780471315186}} the probability of such an event for the case when $\backslash lambda\_1,\; \backslash ldots,\; \backslash 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 $\backslash lambda\_1,\; \backslash ldots,\; \backslash lambda\_n$. In this way even for the worst case of $k=1$ and $f(x)=(x-\backslash 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$.

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\_\{i=0\}^k\; \backslash binom\{k\}\{i\}\; (-z)^\{k-i\}x^i$, we may transition from $f(x)$ to $f(x-z)$ in $O(n^2)$ time.
2. Polynomial multiplication and taking remainder of one polynomial modulo another one may be done in $O(n^2)$, thus calculation of $x^\{2^k\}\; \backslash bmod\; f\_z(x)$ is done in $O(n^2\; \backslash log\; p)$.
3. Binary exponentiation works in $O(n^2\; \backslash log\; p)$.
4. Taking the $\backslash gcd$ of two polynomials via Euclidean algorithm works in $O(n^2)$.

Thus the whole procedure may be done in $O(n^2\; \backslash log\; p)$. Using the fast Fourier transform and Half-GCD algorithm,{{cite book | author = Aho, Alfred V. | url = https://archive.org/details/designanalysisof00ahoarich | title = The design and analysis of computer algorithms | date = 1974 | publisher = Addison-Wesley Pub. Co | isbn = 0201000296 | url-access = registration }} the algorithm's complexity may be improved to $O(n\; \backslash log\; n\; \backslash 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(\backslash log\; p)$ per iteration.

{{reflist}}

{{Number-theoretic algorithms}}

Category:Algorithms

Category:Algebra

Category:Number theoretic algorithms

Category:Polynomials