Abstract:
   Let Q be an n*n symmetric matrix with integral entries and with det Q not 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 the rationals, a solution can be deduced from another quadratic equation of determinant 1 or -1. The combination of these algorithms allows us to solve efficiently any general ternary quadratic equation over the rationals, and this gives a polynomial time algorithm (as soon as the factorization of the determinant of Q is known).

The corresponding GP programs are available.

Résumé :
   Soit Q une matrice symétrique n*n à coefficients entiers et telle que det Q est non nul, mais pas nécesairement définie positive. Nous proposons une généralisation de l'algorithme LLL pour réduire cette forme quadratique. Ou bien cet algorithme réduit la forme quadratique, ou bien il s'arrête avec un vecteur isotrope. La complexité est polynomiale. Nous décrivons aussi un algorithme pour la minimisation d'une forme quadratique ternaire : quand une équation quadratique q(x,y,z)=0 a une solution rationnelle, alors une telle solution peut être déduite de celle d'une autre equation quadratique de déterminant 1 ou -1. La combinaison de ces deux algorithmes permet de résoudre efficacement n'importe quelle équation quadratique ternaire sur les rationnels, en temps polynomial (excepté pour la factorisation du déterminant).

Les programmes GP correspondants sont disponibles.