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

    Join Date
    Jun 2009
    Rep Power

    Shanks Algorithm

    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 ?
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

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

    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:

    (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:

    (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.

IMN logo majestic logo threadwatch logo seochat tools logo