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?)

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