Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Solving quadratic equations using reduced unimodular quadratic forms
HTML articles powered by AMS MathViewer

by Denis Simon PDF
Math. Comp. 74 (2005), 1531-1543 Request permission

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
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
  • Email: simon@math.unicaen.fr
  • Received by editor(s): February 14, 2003
  • Received by editor(s) in revised form: February 26, 2004
  • Published electronically: January 27, 2005
  • © Copyright 2005 American Mathematical Society
  • Journal: Math. Comp. 74 (2005), 1531-1543
  • MSC (2000): Primary 11Y50, 11E20; Secondary 11H55
  • DOI: https://doi.org/10.1090/S0025-5718-05-01729-1
  • MathSciNet review: 2137016