Mathematics of Computation

Author(s): J. E. Cremona; D. Rusin.
Journal: Math. Comp. 72 (2003), 1417-1441.
MSC (2000): Primary 11G30, 11D41
Posted: December 18, 2002
Retrieve article in: PDF

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.

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 http://www.maths.nott.ac.uk/personal/jec/papers/d2.ps.
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.

J. E. Cremona
Affiliation: School of Mathematical Sciences, University of Nottingham, University Park, Nottingham NG7 2RD, United Kingdom
Email: John.Cremona@nottingham.ac.uk

D. Rusin
Affiliation: Department of Mathematical Sciences, Northern Illinois University, DeKalb, Illinois 60115
Email: rusin@math.niu.edu

DOI: 10.1090/S0025-5718-02-01480-1
PII: S 0025-5718(02)01480-1
Received by editor(s): September 5, 2001
Posted: December 18, 2002
Copyright of article: Copyright 2002, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS