Berlekamp–Rabin algorithm

Let ${\textstyle 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 ${\textstyle f_{z}(x)=f(x-z)=(x-\lambda _{1}-z)(x-\lambda _{2}-z)\cdots (x-\lambda _{n}-z)}$ where ${\displaystyle z}$ is some any element of ${\displaystyle \mathbb {Z} _{p}}$. If one can represent this polynomial as the product ${\displaystyle f_{z}(x)=p_{0}(x)p_{1}(x)}$ then in terms of the initial polynomial it means that ${\displaystyle f(x)=p_{0}(x+z)p_{1}(x+z)}$, which provides needed factorization of ${\displaystyle f(x)}$.[1][7]

Due to Euler's criterion, for every monomial ${\displaystyle (x-\lambda )}$ exactly one of following properties holds:[1]

1. The monomial is equal to ${\displaystyle x}$ if ${\displaystyle \lambda =0}$,
2. The monomial divides ${\textstyle g_{0}(x)=(x^{(p-1)/2}-1)}$ if ${\displaystyle \lambda }$ is quadratic residue modulo ${\displaystyle p}$,
3. The monomial divides ${\textstyle g_{1}(x)=(x^{(p-1)/2}+1)}$ if ${\displaystyle \lambda }$ is quadratic non-residual modulo ${\displaystyle p}$.

Thus if ${\displaystyle f_{z}(x)}$ is not divisible by ${\displaystyle x}$, which may be checked separately, then ${\displaystyle f_{z}(x)}$ is equal to the product of greatest common divisors ${\displaystyle \gcd(f_{z}(x);g_{0}(x))}$ and ${\displaystyle \gcd(f_{z}(x);g_{1}(x))}$.[7]

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

1. Explicitly calculate coefficients of ${\displaystyle f_{z}(x)=f(x-z)}$,
2. Calculate remainders of ${\textstyle x,x^{2},x^{2^{2}},x^{2^{3}},x^{2^{4}},\ldots ,x^{2^{\lfloor \log _{2}p\rfloor }}}$ modulo ${\displaystyle f_{z}(x)}$ by squaring the current polynomial and taking remainder modulo ${\displaystyle f_{z}(x)}$,
3. Using exponentiation by squaring and polynomials calculated on the previous steps calculate the remainder of ${\textstyle x^{(p-1)/2}}$ modulo ${\textstyle f_{z}(x)}$,
4. If ${\textstyle x^{(p-1)/2}\not \equiv \pm 1{\pmod {f_{z}(x)}}}$ then ${\displaystyle \gcd }$ mentioned above provide a non-trivial factorization of ${\displaystyle f_{z}(x)}$,
5. Otherwise all roots of ${\displaystyle f_{z}(x)}$ are either residues or non-residues simultaneously and one has to choose another ${\displaystyle z}$.

If ${\displaystyle f(x)}$ is divisible by some non-linear primitive polynomial ${\displaystyle g(x)}$ over ${\displaystyle \mathbb {Z} _{p}}$ then when calculating ${\displaystyle \gcd }$ with ${\displaystyle g_{0}(x)}$ and ${\displaystyle g_{1}(x)}$ one will obtain a non-trivial factorization of ${\displaystyle f_{z}(x)/g_{z}(x)}$, thus algorithm allows to find all roots of arbitrary polynomials over ${\displaystyle \mathbb {Z} _{p}}$.

Consider equation ${\textstyle x^{2}\equiv a{\pmod {p}}}$ having elements ${\displaystyle \beta }$ and ${\displaystyle -\beta }$ as its roots. Solution of this equation is equivalent to factorization of polynomial ${\textstyle f(x)=x^{2}-a=(x-\beta )(x+\beta )}$ over ${\displaystyle \mathbb {Z} _{p}}$. In this particular case problem it is sufficient to calculate only ${\displaystyle \gcd(f_{z}(x);g_{0}(x))}$. For this polynomial exactly one of the following properties will hold:

1. GCD is equal to ${\displaystyle 1}$ which means that ${\displaystyle z+\beta }$ and ${\displaystyle z-\beta }$ are both quadratic non-residues,
2. GCD is equal to ${\displaystyle f_{z}(x)}$which means that both numbers are quadratic residues,
3. GCD is equal to ${\displaystyle (x-t)}$which means that exactly one of these numbers is quadratic residue.

In the third case GCD is equal to either ${\displaystyle (x-z-\beta )}$ or ${\displaystyle (x-z+\beta )}$. It allows to write the solution as ${\textstyle \beta =(t-z){\pmod {p}}}$.[1]

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

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

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

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