Loading ...
Sorry, an error occurred while loading the content.

Re: qfbsolve exercise

Expand Messages
  • djbroadhurst
    ... Not the square root. Think Chinese: since p is a semiprime, there are *two* essentially different square roots, not related by an overall change of sign.
    Message 1 of 4 , Oct 4, 2010
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      Kermit Rose <kermit@...> wrote:

      > > Exercise: Find two pairs of positive integers (x,y) such that
      > > 5*x^2 + 5*x*y + y^2 = (137^137 + 1992)*(137^137 + 3464)

      > Thank you.
      > Now it is clear that 5 is indeed a quadratic residue of
      > p = (137^137 + 1992)*(137^137 + 3464)
      > And therefore, once we find the sqrt(5) mod p ...

      Not "the" square root. Think Chinese: since p is a
      semiprime, there are *two* essentially different square
      roots, not related by an overall change of sign. You should
      use Tonelli-Shanks for these square roots, if you want to do
      it all by yourself, which is of course the best way to learn.
      And then you may use powers of the square of the unit
      (1 + sqrt(5))/2 to shift solutions to the required region with
      x > 0 and y > 0. More efficiently, you may use an Euclidean
      algorithm to do this, as per Cornacchia-Smith, in Cohen 1.5.2,
      or CP 2.3.12.

      Best regards

      David
    Your message has been successfully submitted and would be delivered to recipients shortly.