Solving quadratic equations using reduced unimodular quadratic forms

Author:
Denis Simon

Journal:
Math. Comp. **74** (2005), 1531-1543

MSC (2000):
Primary 11Y50, 11E20; Secondary 11H55

Published electronically:
January 27, 2005

MathSciNet review:
2137016

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let be an symmetric matrix with integral entries and with , but not necesarily positive definite. We describe a generalized LLL algorithm to reduce this quadratic form. This algorithm either reduces the quadratic form or stops with some isotropic vector. It is proved to run in polynomial time. We also describe an algorithm for the minimization of a ternary quadratic form: when a quadratic equation is solvable over , a solution can be deduced from another quadratic equation of determinant . The combination of these algorithms allows us to solve efficiently any general ternary quadratic equation over , and this gives a polynomial time algorithm (as soon as the factorization of the determinant of is known).

**1.**J. W. S. Cassels,*Rational quadratic forms*, London Mathematical Society Monographs, vol. 13, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR**522835****2.**Todd Cochrane and Patrick Mitchell,*Small solutions of the Legendre equation*, J. Number Theory**70**(1998), no. 1, 62–66. MR**1619944**, 10.1006/jnth.1998.2221**3.**Henri Cohen,*A course in computational algebraic number theory*, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR**1228206****4.**J. E. Cremona and D. Rusin,*Efficient solution of rational conics*, Math. Comp.**72**(2003), no. 243, 1417–1441 (electronic). MR**1972744**, 10.1090/S0025-5718-02-01480-1**5.**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****6.**Jean-Pierre Serre,*Cours d’arithmétique*, Presses Universitaires de France, Paris, 1977 (French). Deuxième édition revue et corrigée; Le Mathématicien, No. 2. MR**0498338****7.**Denis Simon,*Solving norm equations in relative number fields using 𝑆-units*, Math. Comp.**71**(2002), no. 239, 1287–1305 (electronic). MR**1898758**, 10.1090/S0025-5718-02-01309-1**8.**Denis Simon,*Computing the rank of elliptic curves over number fields*, LMS J. Comput. Math.**5**(2002), 7–17 (electronic). MR**1916919**, 10.1112/S1461157000000668**9.**Nigel P. Smart,*The algorithmic resolution of Diophantine equations*, London Mathematical Society Student Texts, vol. 41, Cambridge University Press, Cambridge, 1998. MR**1689189****10.**Brigitte Vallée,*An affine point of view on minima finding in integer lattices of lower dimensions*, EUROCAL ’87 (Leipzig, 1987) Lecture Notes in Comput. Sci., vol. 378, Springer, Berlin, 1989, pp. 376–378. MR**1033317**, 10.1007/3-540-51517-8_141

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11Y50,
11E20,
11H55

Retrieve articles in all journals with MSC (2000): 11Y50, 11E20, 11H55

Additional Information

**Denis Simon**

Affiliation:
LMNO–UMR 6139, Université de Caen–Campus II, Bd du Maréchal Juin, BP 5186–14032 Caen Cedex, France

Email:
simon@math.unicaen.fr

DOI:
http://dx.doi.org/10.1090/S0025-5718-05-01729-1

Keywords:
Quadratic equation,
algorithm

Received by editor(s):
February 14, 2003

Received by editor(s) in revised form:
February 26, 2004

Published electronically:
January 27, 2005

Article copyright:
© Copyright 2005
American Mathematical Society