Efficient Solution of Rational Conics - Cremona, John E; Rusin, David (American Mathematical Society, 2001)
We present efficient algorithms for solving Legendre equations over Q (equivalently, for finding rational points on rational conics) and parametrizing all solutions. Unlike existing algorithms, no integer factorization is required, provided that the prime factors of the discriminant are known.