October 21st, 2009, 07:34 AM

Shanks Algorithm
i am trying to implement shanks algorithm but im stuck at geting a quadratic residue.
i have been reading 
http://mathforum.org/library/drmath/view/65305.html
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, 12:53 PM

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:
Code:
(x^2  x0^2) = 0 mod(p)
I no longer recall the names of these algebraic rules, but the next step removes the exponents ^2 from the equation:
[code]
(xx0)(x+x0) = 0 mod(p)
[code]
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.