Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Efficient solution of rational conics

Authors: J. E. Cremona and D. Rusin
Journal: Math. Comp. 72 (2003), 1417-1441
MSC (2000): Primary 11G30, 11D41
Published electronically: December 18, 2002
MathSciNet review: 1972744
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present efficient algorithms for solving Legendre equations over $\mathbb 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.

References [Enhancements On Off] (What's this?)

  • 1. B. J. Birch and H. P. F. Swinnerton-Dyer, Notes on elliptic curves II, J. Reine Angew. Math. 218 (1965), 79-108. MR 31:3419
  • 2. J. W. S. Cassels, Lectures on elliptic curves, London Mathematical Society Student Texts, no. 24, Cambridge University Press, 1991. MR 92k:11058
  • 3. T. Cochrane and P. Mitchell, Small solutions of the Legendre equation, Journal of Number Theory 70 (1998), 62-66. MR 99a:11029
  • 4. H. Cohen, A course in computational algebraic number theory (third corrected printing), Graduate Texts in Mathematics, no. 138, Springer-Verlag, 1996. MR 94i:11105
  • 5. J. E. Cremona, Higher descents on elliptic curves, preprint: see
  • 6. I. Gaál, A. Petho, and M. Pohst, Simultaneous representation of integers by a pair of ternary quadratic forms-with an application to index form equations in quartic number fields, Journal of Number Theory 57 (1996), 90-104. MR 96m:11026
  • 7. C. F. Gauss, Disquisitiones arithmeticae, Springer-Verlag, 1986. MR 87f:01105
  • 8. K. Ireland and M. Rosen, A classical introduction to modern number theory, Graduate Texts in Mathematics, no. 84, Springer-Verlag, 1982. MR 83g:12001
  • 9. B. Mazur, On the passage from local to global in number theory, Bull. Amer. Math. Soc. (N.S.) 29 (1993), no. 1, 14-50. MR 93m:11052
  • 10. L. J. Mordell, Diophantine equations, Pure and Applied Mathematics, no. 30, Academic Press, 1969. MR 40:2600
  • 11. M. Pohst, On Legendre's equation over number fields, Publ. Math. (Debrecen) 56 (2000), 535-546. MR 2001f:11106
  • 12. J. M. Pollard and C. P. Schnorr, An efficient solution of the congruence $X^2+kY^2\equiv m\pmod{n}$, IEEE Transactions on Information Theory 33 (1987), no. 5, 702-709. MR 89e:11080
  • 13. H. Rolletschek, On the number of divisions of the euclidean algorithm applied to gaussian integers, J. Symb, Comput. 2 (1986), 261-291. MR 88d:11131
  • 14. D. Simon, Équations dans les corps de nombres et discriminants minimaux, Ph.D. thesis, Université Bordeaux I, 1998.
  • 15. N. P. Smart, The algorithmic resolution of Diophantine equations: a computational cookbook, London Mathematical Society Lecture Notes Series, no. 117, Cambridge University Press, 1998. MR 2000c:11208
  • 16. B. Vallée, Algorithmique dans les réseaux de petite dimension: un point de vue affine sur la récherche des minima, Séminaire de Théorie des nombres de Bordeaux (1985-1986), no. 13. MR 88h:11097
  • 17. H.-J. Weber, Algorithmische Konstruktion hyperelliptischer Kurven mit kryptographischer Relevanz und einem Endomorphismenring echt größer als Z, Ph.D. thesis, Institut für Experimentelle Mathematik, University of Essen, 1997.
  • 18. A. Weil, Number theory: an approach through history from Hammurapi to Legendre, Birkhäuser, 1984. MR 85c:01004
  • 19. J. Wilson, Curves of genus 2 with real multiplication by a square root of 5, Ph.D. thesis, University of Oxford, 1998.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11G30, 11D41

Retrieve articles in all journals with MSC (2000): 11G30, 11D41

Additional Information

J. E. Cremona
Affiliation: School of Mathematical Sciences, University of Nottingham, University Park, Nottingham NG7 2RD, United Kingdom

D. Rusin
Affiliation: Department of Mathematical Sciences, Northern Illinois University, DeKalb, Illinois 60115

Received by editor(s): September 5, 2001
Published electronically: December 18, 2002
Article copyright: © Copyright 2002 American Mathematical Society

American Mathematical Society