Content deleted Content added
→top: #suggestededit-add-image-top Tags: Mobile edit Mobile app edit Android app edit |
m The text mentioned the gcd description was "above" but it is actually below the mention of the non-trivial solution being the gcd |
||
Line 30:
# Calculate remainders of <math display="inline">x,x^2, x^{2^2},x^{2^3}, x^{2^4}, \ldots, x^{2^{\lfloor \log_2 p \rfloor}}</math> modulo <math>f_z(x)</math> by squaring the current polynomial and taking remainder modulo <math>f_z(x)</math>,
# Using [[exponentiation by squaring]] and polynomials calculated on the previous steps calculate the remainder of <math display="inline">x^{(p-1)/2}</math> modulo <math display="inline">f_z(x)</math>,
# If <math display="inline">x^{(p-1)/2} \not \equiv \pm 1 \pmod{f_z(x)}</math> then <math>\gcd</math> mentioned
# Otherwise all roots of <math>f_z(x)</math> are either residues or non-residues simultaneously and one has to choose another <math>z</math>.
| |||