1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jun 2009
Posts
9
Rep Power
0

#### Shanks Algorithm

i am trying to implement shanks algorithm but im stuck at geting a quadratic residue.
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)

2. No Profile Picture
Contributing User
Devshed Loyal (3000 - 3499 posts)

Join Date
May 2004
Posts
3,417
Rep Power
887
Afraid my formal math skills are bit rusty these days, but:

Code:
`x^2 = x0^2 	      (mod p)`
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]
(x-x0)(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.