Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



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 $Q$ be an $n\times n$ symmetric matrix with integral entries and with $\det Q \neq 0$, 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 $q(x,y,z)=0$ is solvable over $\mathbb{Q} $, a solution can be deduced from another quadratic equation of determinant $\pm 1$. The combination of these algorithms allows us to solve efficiently any general ternary quadratic equation over $\mathbb{Q} $, and this gives a polynomial time algorithm (as soon as the factorization of the determinant of $Q$ is known).

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

  • 1. J.W.S. Cassels: Rational Quadratic Forms, L.M.S. Monographs, No.13. London, New York, San Francisco: Academic Press (1978). MR 0522835 (80m:10019)
  • 2. T. Cochrane and P. Mitchell: Small solutions of the Legendre equation, Journal of Number Theory 70 (1998), 62-66. MR 1619944 (99a:11029)
  • 3. H. Cohen: A Course in Computational Algebraic Number Theory, Graduate Texts in Math. 138, Third corrected printing, Springer-Verlag (1996). MR 1228206 (94i:11105)
  • 4. J.E. Cremona, D. Rusin: Efficient solution of rational conics, Math. Comp. 72 (2003), 1417-1441. MR 1972744 (2004a:11137)
  • 5. C.F. Gauss: Disquisitiones Arithmeticae, Springer Verlag (1986). MR 0837656 (87f:01105)
  • 6. J.-P. Serre: Cours d'arithmétique, P.U.F. 3d edition (1988). MR 0498338 (58:16473)
  • 7. D. Simon: Solving norm equations in relative number fields using S-units, Math. Comp., vol. 71 No. 239 (2002), 1287 - 1305. MR 1898758 (2003d:11044)
  • 8. D. Simon: Computing the rank of elliptic curves over number fields, London Math. Soc. Journal of Computation and Mathematics, vol. 5 (2002), 7-17. MR 1916919 (2003g:11060)
  • 9. N.P. Smart: The algorithmic resolution of Diophantine equations, London Math. Soc. Student Texts 41, Cambridge University Press, 1998. MR 1689189 (2000c:11208)
  • 10. B. Vallée: An affine point of view on minima finding in integer lattices of lower dimensions, Proc. of EUROCAL '87 (Leipzig, 1987), Lecture Notes in Comput. Sci. 378, Springer, Berlin, 1989, 376-378. MR 1033317 (92d:11069)

Similar Articles

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

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

American Mathematical Society