Tenth Algorithmic Number Theory Symposium ANTS-X University of California, San Diego July 9 – 13, 2012 Tenth Algorithmic Number Theory Symposium (ANTS-X) July 9 – 13, 2012

Solving quadratic equations in dimension 5 or more without factoring

Pierre Castel

Abstract: Let Q be a 5 x 5 symmetric matrix with integral entries and with det Q != 0, but neither positive nor negative definite. We describe a probabilistic algorithm which solves the equation x^t Q x = 0 over Z without factoring det Q. The method can easily be generalized to forms of higher dimensions by reduction to a suitable subspace.

Files available: paper (PDF), slides