##
Friedrich Eisenbrand and Günter Rote:

#
Fast reduction of ternary quadratic forms

*In: Cryptography and Lattices—International Conference, CaLC
2001, Providence, Rhode Island, March 29–30, 2001, Revised
Papers. Editor: Joseph H. Silverman. Lecture Notes in Computer
Science 2146, Springer-Verlag, 2001, pp. 32–44. *doi:10.1007/3-540-44670-2_4
###
Abstract

We show that a positive definite integral ternary form can be reduced with
*O*(*M*(*s*)log^{2}*s*) bit operations, where
*s* is the binary encoding length of the form and *M*(*s*)
is the bit-complexity of *s*-bit integer multiplication.
This result is achieved in two steps. First we prove that the the classical
Gaussian algorithm for ternary form reduction, in the variant of Lagarias,
has this worst case running time. Then we show that, given a ternary form
which is reduced in the Gaussian sense, it takes only a constant number
of arithmetic operations and a constant number of binary-form reductions
to fully reduce the form.

Finally we describe how this algorithm can be generalized to higher
dimensions. Lattice basis reduction and shortest vector computation in
fixed dimension *d* can be done with *O*(*M*(*s*)log^{d-1}*s*)
bit-operations.

Last update: March 20, 2002.