Content deleted Content added
→top: authorlink, and gosh there are a lot of unused parameters in here |
→Algorithm: move punc before refs |
||
Line 10:
=== Randomization ===
Let <math display="inline">f(x) = (x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_n)</math>. 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 <math display="inline">f_z(x)=f(x-z) = (x-\lambda_1 - z)(x-\lambda_2 - z) \cdots (x-\lambda_n-z)</math> where <math>z</math> is some any element of <math>\mathbb Z_p</math>. If one can represent this polynomial as the product <math>f_z(x)=p_0(x)p_1(x)</math> then in terms of the initial polynomial it means that <math>f(x) =p_0(x+z)p_1(x+z)</math>, which provides needed factorization of <math>f(x)</math>.<ref name=":0" /><ref name=":2" />
=== Classification of <math>\mathbb Z_p</math> elements ===
Line 19:
# The monomial divides <math display="inline">g_1(x)=(x^{(p-1)/2}+1)</math> if <math>\lambda</math> is quadratic non-residual modulo <math>p</math>.
Thus if <math>f_z(x)</math> is not divisible by <math>x</math>, which may be checked separately, then <math>f_z(x)</math> is equal to the product of [[Polynomial greatest common divisor|greatest common divisors]] <math>\gcd(f_z(x);g_0(x))</math> and <math>\gcd(f_z(x);g_1(x))</math>.<ref name=":2" />
=== Berlekamp's method ===
Line 39:
# GCD is equal to <math>(x-t)</math>which means that exactly one of these numbers is quadratic residue.
In the third case GCD is equal to either <math>(x-z-\beta)</math> or <math>(x-z+\beta)</math>. It allows to write the solution as <math display="inline">\beta = (t - z) \pmod{p}</math>.<ref name=":0" />
=== Example ===
| |||