Efficient solution of rational conics

Cremona, J.; Rusin, D.

doi:10.1090/S0025-5718-02-01480-1

Efficient solution of rational conics
HTML articles powered by AMS MathViewer

by J. E. Cremona and D. Rusin PDF

Math. Comp. 72 (2003), 1417-1441 Request permission

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

B. J. Birch and H. P. F. Swinnerton-Dyer, Notes on elliptic curves. II, J. Reine Angew. Math. 218 (1965), 79–108. MR 179168, DOI 10.1515/crll.1965.218.79
J. W. S. Cassels, Lectures on elliptic curves, London Mathematical Society Student Texts, vol. 24, Cambridge University Press, Cambridge, 1991. MR 1144763, DOI 10.1017/CBO9781139172530
Todd Cochrane and Patrick Mitchell, Small solutions of the Legendre equation, J. Number Theory 70 (1998), no. 1, 62–66. MR 1619944, DOI 10.1006/jnth.1998.2221
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
J. E. Cremona, Higher descents on elliptic curves, preprint: see http://www.maths.nott.ac.uk/personal/jec/papers/d2.ps.
István Gaál, Attila Pethő, and Michael Pohst, Simultaneous representation of integers by a pair of ternary quadratic forms—with an application to index form equations in quartic number fields, J. Number Theory 57 (1996), no. 1, 90–104. MR 1378574, DOI 10.1006/jnth.1996.0035
Carl Friedrich Gauss, Disquisitiones arithmeticae, Springer-Verlag, New York, 1986. Translated and with a preface by Arthur A. Clarke; Revised by William C. Waterhouse, Cornelius Greither and A. W. Grootendorst and with a preface by Waterhouse. MR 837656
Kenneth F. Ireland and Michael I. Rosen, A classical introduction to modern number theory, Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York-Berlin, 1982. Revised edition of Elements of number theory. MR 661047
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 1202293, DOI 10.1090/S0273-0979-1993-00414-2
L. J. Mordell, Diophantine equations, Pure and Applied Mathematics, Vol. 30, Academic Press, London-New York, 1969. MR 0249355
Michael E. Pohst, On Legendre’s equation over number fields, Publ. Math. Debrecen 56 (2000), no. 3-4, 535–546. Dedicated to Professor Kálmán Győry on the occasion of his 60th birthday. MR 1765998
John M. Pollard and Claus-P. Schnorr, An efficient solution of the congruence $x^2+ky^2=m\pmod n$, IEEE Trans. Inform. Theory 33 (1987), no. 5, 702–709. MR 918192, DOI 10.1109/TIT.1987.1057350
Heinrich Rolletschek, On the number of divisions of the Euclidean algorithm applied to Gaussian integers, J. Symbolic Comput. 2 (1986), no. 3, 261–291. MR 860539, DOI 10.1016/S0747-7171(86)80027-X
D. Simon, Équations dans les corps de nombres et discriminants minimaux, Ph.D. thesis, Université Bordeaux I, 1998.
Nigel P. Smart, The algorithmic resolution of Diophantine equations, London Mathematical Society Student Texts, vol. 41, Cambridge University Press, Cambridge, 1998. MR 1689189, DOI 10.1017/CBO9781107359994
Brigitte Vallée, Algorithmique dans les réseaux de petite dimension: un point de vue affine sur la recherche des minima, Séminaire de théorie des nombres, 1985–1986 (Talence, 1985–1986) Univ. Bordeaux I, Talence, 1986, pp. Exp. No. 13, 15 (French). MR 883094
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.
André Weil, Number theory, Birkhäuser Boston, Inc., Boston, MA, 1984. An approach through history; From Hammurapi to Legendre. MR 734177, DOI 10.1007/978-0-8176-4571-7
J. Wilson, Curves of genus 2 with real multiplication by a square root of 5, Ph.D. thesis, University of Oxford, 1998.