Re: qfbsolve exercise
- --- In firstname.lastname@example.org,
Kermit Rose <kermit@...> wrote:
> > Exercise: Find two pairs of positive integers (x,y) such thatNot "the" square root. Think Chinese: since p is a
> > 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 ...
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.