×

zbMATH — the first resource for mathematics

Solving quadratic equations using reduced unimodular quadratic forms. (English) Zbl 1078.11072
The author considers indefinite quadratic forms with integer coefficients and gives a polynomial time algorithm (based on LLL) to reduce it to a diagonal form. Further, an algorithm is given for the minimization of a ternary quadratic form: if a quadratic equation \(q(x,y,z)=0\) is solvable over the rationals, a solution can be deduced from another quadratic form equation of determinant \(\pm 1\). Combining these methods we obtain a polynomial time algorithm to solve any ternary quadratic equation over the rationals. The paper is illustrated with interesting examples.

MSC:
11Y50 Computer solution of Diophantine equations
11E20 General ternary and quaternary quadratic forms; forms of more than two variables
11H55 Quadratic forms (reduction theory, extreme forms, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[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. · Zbl 0395.10029
[2] Todd Cochrane and Patrick Mitchell, Small solutions of the Legendre equation, J. Number Theory 70 (1998), no. 1, 62 – 66. · Zbl 0908.11012
[3] Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. · Zbl 0786.11071
[4] J. E. Cremona and D. Rusin, Efficient solution of rational conics, Math. Comp. 72 (2003), no. 243, 1417 – 1441. · Zbl 1022.11031
[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. · Zbl 0136.32301
[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. · Zbl 0376.12001
[7] Denis Simon, Solving norm equations in relative number fields using \?-units, Math. Comp. 71 (2002), no. 239, 1287 – 1305. · Zbl 0990.11014
[8] Denis Simon, Computing the rank of elliptic curves over number fields, LMS J. Comput. Math. 5 (2002), 7 – 17. · Zbl 1067.11015
[9] Nigel P. Smart, The algorithmic resolution of Diophantine equations, London Mathematical Society Student Texts, vol. 41, Cambridge University Press, Cambridge, 1998. · Zbl 0907.11001
[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. · Zbl 1209.11109
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.