October 21st, 2009, 06:34 AM
i am trying to implement shanks algorithm but im stuck at geting a quadratic residue.
i have been reading -
but i really don't get
x^2 = x0^2 (mod p)
(x^2 - x0^2) = 0 (mod p)
(x - x0)(x + x0) = 0 (mod p)
can anyone help please ?
October 21st, 2009, 11:53 AM
Afraid my formal math skills are bit rusty these days, but:
That's an equation. There exists some x such that xx == x0x0 (mod p). Note that mod(p) applies to both sides of the equation. All of the arithmatic will performed modulo some prime number p. It's a fairly simple premise actually. Now you can apply certain algebraic rules to solve for x mod(p) and they seem to have done just that. In order to solve for x mod(p) they must move all the x's to one side of the equation and then whatever remains on the other side is the solution for x mod(p). It just happens to be a convention to wind up with the result on the right so they shift to x's over to the left. In order to do this and still maintain equality, any positive x on the right becomes a negative x on the left:
I no longer recall the names of these algebraic rules, but the next step removes the exponents ^2 from the equation:
(x^2 - x0^2) = 0 mod(p)
(x-x0)(x+x0) = 0 mod(p)
Note that I used code tags to preserved the space between the equation and modulus specifier. It just means that all the numbers are expressed using modulus p arithmetic.
I believe they went to all this trouble to make some points regarding the effective truthfulness of the equation, depending on whether p is prime or not, but I am not sure I grok their logic completely yet.
I no longer wish to be associated with this site.