1:01

1:02

1:03 1:04 1:05 1:06

1:07 1:08 1:09 1:10 1:11 1:12 1:13 1:14 1:15 1:16 1:17 1:18 1:19

1:20

1:21 1:22

1:23

1:24 1:25 1:26 1:27 1:28 1:29

1:30

1:31 1:32 1:33 1:34 1:35

Fast Reduction of Ternary Quadratic Forms

Friedrich Eisenbrand^{1} and Günter Rote^{2}

1 Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken,

                 Germany, eisen@mpi-sb.mpg.de

2 Institut für Informatik, Freie Universität Berlin, Takustraße 9, 14195 Berlin,

                Germany, rote@inf.fu-berlin.de

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.

1 Introduction

A positive definite integral quadratic form F, or form for short, is a homogeneous polynomial

F (X_{1}, …, X_{d}) = (X_{1}, …, X_{d}) A (X_{1}, …, X_{d})^{T},

where A ∈ ℤ^{d×d} is an integral positive definite matrix, i.e., A = A^{T} and x^{T}Ax > 0 for all x ≠ 0. The study of forms is a fundamental topic in the geometry of numbers (see, e.g., [2]). A basic question here is: Given a form F, what is the minimal nonzero value λ(F) = min{ F (x_{1}, …, x_{d}) | x ∈ ℤ^{d}, x ≠ 0 } of the form which is attained at an integral vector? This problem will be of central interest in this paper.

Problem 1. Given a form F, compute λ(F).

At least since Lenstra’s [9] polynomial algorithm for integer programming in fixed dimension, the study of quadratic forms has also become a major topic in theoretical computer science. Here, one is interested in the lattice variant of Problem 1, which is: Given a basis of an integral lattice, find a shortest nonzero vector of the lattice w.r.t. the ℓ_{2}-norm.

2:01 2:02 2:03

2:04

2:05 2:06 2:07 2:08 2:09 2:10 2:11 2:12 2:13 2:14 2:15 2:16 2:17 2:18 2:19 2:20 2:21 2:22 2:23 2:24 2:25 2:26 2:27 2:28 2:29 2:30 2:31 2:32 2:33

2:34 2:35 2:36 2:37 2:38 2:39 2:40 2:41

In fixed dimension, Problem 1 can be quickly solved if F is reduced (see Theorem 4 in Sect. 5). In our setting, this shall mean that the product of the diagonal elements of A satisfies

∏_{i=1}^{d} a_{ii} ≤ γ_{d} Δ_{F}  (1)

for some constant γ_{d} depending on the dimension d only. Here Δ_{F} = det A is the determinant of the form F. Algorithms which transform a form F into an equivalent reduced form are called reduction algorithms.

In algorithmic number theory, the cost measure that is widely used in the analysis of algorithms is the number of required bit operations. The famous LLL algorithm [8] is a reduction algorithm which has polynomial running time, even in varying dimension. In fixed dimension, the LLL reduction algorithm reduces a form F of binary encoding size s with O(s) arithmetic operations on integers of size O(s). This amounts to O(M(s) s) bit-operations, where M(s) is the bitcomplexity of s-bit integer multiplication. If one plugs in the current record for M(s) = O(s log s log log s) [11], this shows that a form F can be reduced with a close to quadratic amount of bit-operations.

A form in two variables is called a binary form. Here one has asymptotically fast reduction algorithms. It was shown by Schönhage [10] and independently by Yap [16] that a binary quadratic form can be reduced with O(M(s) log s) bit-operations, see also Eisenbrand [3] for an easier approach.

In his famous disquisitiones arithmeticae [4], Gauß provided a “reduction algorithm” for forms in three variables, called ternary forms. He showed how to compute a ternary form, equivalent to a given form, such that the first diagonal element of the coefficient matrix is at most \frac{4}{3} \sqrt[3]{Δ_{F}}. A form which is reduced in the Gaussian sense is not necessarily reduced in the sense of (1). The Gaussian notion of reduction was modified by Seeber [13] such that a reduced form satisfies (1) with γ_{3} = 3. Gauß [5] showed later that γ_{3} = 2.

The “reduction algorithm” of Gauß was modified by Lagarias [7] to produce so called quasi-reduced forms. They satisfy the slightly weaker condition that the first diagonal element is at most twice the cubic root of the determinant. Lagarias proved that his modified ternary form algorithm runs in polynomial time. However, a quasi-reduced form is not necessarily reduced in the sense of (1).

Results. We prove that ternary forms can be reduced with a close to linear amount of bit-operations, as it is the case for binary forms. More precisely, a ternary form F of binary encoding length s can be reduced in the sense of (1) with γ_{3} = \frac{16}{3} using O(M(s) log^{2} s) bit-operations. Unfortunately, the complexity of the proposed reduction procedure has still an extra (log s)-factor compared to the complexity of binary form reduction. However our result largely improves on the O(M(s) s) complexity of algorithms for ternary form reduction which are based on the LLL algorithm.

3:01 3:02 3:03 3:04 3:05 3:06 3:07 3:08 3:09 3:10 3:11

3:12 3:13 3:14 3:15 3:16 3:17 3:18 3:19 3:20

3:21

3:22 3:23 3:24 3:25 3:26 3:27 3:28

3:29

3:30 3:31 3:32 3:33 3:34 3:35 3:36 3:37 3:38 3:39 3:40

We proceed as follows. First we show that the Gaussian ternary form algorithm, in the variant of Lagarias [7], requires O(M(s) log^{2} s) bit-operations. This is achieved via a refinement of the analysis given by Lagarias. Then we prove that, given a quasi-reduced ternary form, it takes at most O(M(s) log s) bit-operations to compute an equivalent reduced form. Therefore, a ternary form can be reduced with O(M(s) log^{2} s) bit-operations. This improves on the best previously known algorithms. It follows that, for ternary forms, Problem 1 can be solved with O(M(s) log^{2} s) bit-operations.

Finally we generalize the described algorithm to any fixed dimension d. The resulting lattice basis reduction algorithm requires O(M(s) log^{d−1} s) bitoperations.

Related work. Apart from the already mentioned articles, three-dimensional lattice reduction was extensively studied by various authors. Vallée [15] invented a generalization of the two-dimensional Gaussian algorithm in three dimensions. Vallée’s algorithm requires O(M(s) s) bit-operations. Semaev [14] provides an algorithm for three-dimensional lattice basis reduction which is based on pair reduction. The running time of his algorithm is O(s^{2}) bit-operations even if one uses the naive quadratic methods for integer multiplication and division. This matches the complexity of the Euclidean algorithm for the greatest common divisor.

2 Preliminaries and Notation

The letters ℤ and ℚ denote the integers and rationals respectively. The running times of algorithms are always given in terms of the binary encoding length of the input data. The cost measure is the amount of bit operations. The function M(s) denotes the bit-complexity of s-bit integer multiplication. All basic arithmetic operations can be done in time O(M(s)) [1].

We will only consider positive definite integral quadratic forms. We identify a form F with its coefficient matrix M_{F} ∈ ℤ^{d×d} such that

F (X_{1}, …, X_{d}) = (X_{1}, …, X_{d}) M_{F} (X_{1}, …, X_{d})^{T}.

The function size(F) denotes the binary encoding length of M_{F}. Two forms F and G are equivalent if there exists a unimodular matrix U ∈ ℤ^{d×d} with M_{G} = U^{T}M_{F} U. We say that U transforms F into G. The number Δ_{F} = det M_{F} is the determinant of the form. The determinant is invariant under equivalence. See, e.g., [2] for more on the theory of quadratic forms. The coefficient matrix M_{F} ∈ ℤ^{d×d} has a unique R^{T}DR factorization, i.e, a factorization M_{F} = R^{T}DR, where R ∈ ℚ^{d×d} is an upper triangular matrix with ones on the diagonal and D is a diagonal matrix. The matrix R has a unique normalization R′ = RU, where U is unimodular and R′ is upper triangular with ones on the diagonal and elements above the diagonal in the range (−\frac{1}{2}, \frac{1}{2}]. The corresponding matrix R′^{T}DR′ defines a form F′ which is equivalent to F. The form F′ is called the

4:01 4:02 4:03 4:04 4:05 4:06

4:07

4:08 4:09

4:10 4:11

4:12 4:13

4:14 4:15 4:16 4:17

4:18 4:19 4:20

4:21

4:22 4:23

4:24

4:25 4:26

4:27

4:28 4:29 4:30 4:31 4:32

Gram-Schmidt normalization of F. This is the normalization step of the LLL algorithm [8], translated into the language of quadratic forms. In fixed dimension, the Gram-Schmidt normalization of a form F of size s can be computed with a constant number of arithmetic operations, and hence with O(M(s)) bitoperations. We say that a form G is a γ-reduction of F, if G is equivalent to F and if the product of the diagonal elements of M_{G} is at most γ Δ_{F}.

2.1 Binary Forms

A binary form is a form in two variables. We denote binary forms with lower case letters f or g. The binary form f is reduced if M_{f} = ( \begin{matrix}a_{11} & a_{12} \\ a_{12} & a_{22} \end{matrix} ) satisfies

a_{11} ≤ a_{22}  (2)
|a_{12}| ≤ \frac{1}{2}a_{11}.  (3)

If f is reduced one has

\frac{3}{4} a_{11} a_{22} ≤ Δ_{f}.  (4)

The unimodular matrix ( \begin{matrix}1 & −r \\ 0 & 1 \end{matrix} ), where r is the nearest integer to \frac{a_{12}}{a_{11}} , transforms a binary form f to an equivalent form which is called the normalization of f. The normalization of f satisfies (3).

We have the following result of Schönhage [10] and Yap [16].

Theorem 1. Given a positive definite integral binary quadratic form f of size s, one can compute with O(M(s) log s) bit-operations an equivalent reduced form g and a unimodular matrix U ∈ ℤ^{2×2} which transforms f into g. ⊓ ⊔

2.2 Ternary Forms

Ternary forms will be denoted by capital letters F or G. Let F be given by its coefficient matrix

M_{F} = (\begin{matrix}a_{11} & a_{12} & a_{13} \\ a_{12} & a_{22} & a_{23} \\ a_{13} & a_{23} & a_{33} \end{matrix}) .

The form F defines associated binary forms f_{ij}, 1 ≤ i, j ≤ 3, i ≠ j which have coefficient matrix

M_{f_{ij}} = (\begin{matrix}a_{ii} & a_{ij} \\ a_{ij} & a_{jj} \end{matrix}) .

By reducing f_{ij} in F, we mean that we compute the unimodular transformation which reduces f_{ij} and apply it to the whole coefficient matrix M_{F}. This changes only the i-th and j-th row and column of M_{F} and leaves the third diagonal element a_{kk} unchanged. It follows from Theorem 1 that such a reduction of f_{ij} in F can be done with O(M(s) log s) bit-operations on forms F of size s.

5:01 5:02

5:03

5:04 5:05 5:06 5:07 5:08 5:09

5:10

5:11

5:12 5:13 5:14

5:15 5:16

5:17

5:18 5:19 5:20 5:21 5:22

5:23

5:24 5:25

5:26 5:27

5:28 5:29

5:30

5:31

5:32

The adjoint F^{∗} of F is defined by the coefficient matrix M_{F^{∗}} = det M_{F} ·M_{F}^{−1} and we write

M_{F^{∗}} = (\begin{matrix}A_{11} & A_{12} & A_{13} \\ A_{12} & A_{22} & A_{23} \\ A_{13} & A_{23} & A_{33} \end{matrix}) .

Clearly M_{F^{∗}} is integral and positive definite. A unimodular matrix S ∈ ℤ^{3×3} transforms F into G if and only if (S^{T})^{−1} transforms F^{∗} into G^{∗}. The associated binary forms of F^{∗} are denoted by f_{ij}^{∗} and by reducing such an associated form in F we mean that we apply the corresponding reduction operations on F. Notice that size(F^{∗}) = O(size(F)) and size(F) = O(size(F^{∗})) and that Δ_{F^{∗}} = Δ_{F}^{2} .

The ternary form F is quasi-reduced (see [7, p. 162]) if

a_{11} ≤ 2 \sqrt[3]{Δ_{F}}  (5)
A_{33} ≤ 2 \sqrt[3]{Δ_{F}^{2}}  (6)
|a_{12}| ≤ \frac{1}{2} a_{11}  (7)
|A_{13}| ≤ \frac{1}{2} A_{33}  (8)
|A_{23}| ≤ \frac{1}{2} A_{33}.  (9)

This notion is a relaxation of Gauß’ concept of reduction of ternary forms, which has the constant 4/3 instead of 2 in (5–6).

3 Computing a Quasi-Reduced Ternary Form

The Gaussian algorithm [4, Arts. 272–275] for ternary form “reduction” proceeds by iteratively reducing the associated binary forms f_{12} and f_{32}^{∗} in F. Lagarias [7] modified the algorithm by keeping the entries above and below the diagonal of the intermediate forms small so that (7–9) are fulfilled after every iteration. So we only have to see that (5) and (6) are fulfilled. One iterates until

A_{33} < 2 \sqrt[3]{Δ_{F}^{2}} .  (10)

In the following we prove that the number of iterations until a ternary form F of size s satisfies (10) is O(log s). For F and its adjoint F^{∗} one has

A_{33} = Δ_{f_{12}}  (11)
a_{11}Δ_{F} = Δ_{f_{32}^{∗}}.

Thus reducing f_{12} in F leaves A_{33} unchanged and reducing f_{32}^{∗} in F leaves a_{11} unchanged. Furthermore, after reducing f_{12} in F one has

a_{11} ≤ \sqrt{\frac{4}{3} A_{33}}  (12)

by (11), (2) and (4). Similarly, after reducing f_{32}^{∗} in F one has

A_{33} ≤ \sqrt{\frac{4}{3} a_{11}Δ_{F}} .  (13)

6:01 6:02 6:03 6:04 6:05

6:06

6:07

6:08

6:09 6:10

6:11

6:12

6:13

6:14

6:15

6:16 6:17 6:18 6:19 6:20 6:21 6:22

6:23 6:24

6:25 6:26 6:27

6:28

6:29 6:30

6:31

This shows that each iteration decreases the binary encoding length of A_{33} by roughly a factor of 4 as long as A_{33} exceeds \sqrt[3]{Δ_{F}^{2}} by a large amount. We make this observation more precise.

Let A_{kl}^{(i)} denote the coefficients of F^{∗} after the i-th iteration of this procedure. By combining (12) and (13) we get the following relation (see [7, p. 166, (4.65)])

A_{33}^{(i+1)} ≤ (\frac{4}{3})^{(3/4)} \sqrt{Δ_{F}} (A_{33}^{(i)})^{1/4}.  (14)

Lagarias then remarks that, if A_{33}^{(i)} ≥ 2 \sqrt[3]{Δ_{F}^{2}} , then

A_{33}^{(i+1)} ≤ (\frac{2}{3})^{3/4} A_{33}^{(i)}  (15)

and it follows that the number of iterations is bounded by O(s). Lagarias does not take full advantage of (14). By rewriting (14) in the form

\frac{A_{33}^{(i+1)}}{\frac{4}{3}Δ_{F}^{2/3}} ≤ \sqrt[4]{\frac{A_{33}^{(i)}}{\frac{4}{3}Δ_{F}^{2/3}}} ,

we see that we can achieve

\frac{A_{33}^{(i+1)}}{\frac{4}{3}Δ_{F}^{2/3}} ≤ 2

in at most

i = log_{4} log_{2} [A_{33}^{(0)}/(\frac{4}{3}Δ_{F}^{2/3})] ≤ log_{4} log_{2} A_{33}^{(0)} = O(log s)

iterations. After we have achieved A_{33}^{(i)} ≤ \frac{8}{3} \sqrt[3]{Δ_{F}^{2}} , then, by (15), the modified ternary form algorithm requires at most one additional iteration to obtain an equivalent quasi-reduced form.

This shows that the modified ternary form algorithm requires O(log s) iterations to quasi-reduce a ternary form of size s. If one iteration of the reduction algorithm is performed with the fast reduction algorithm for binary forms one obtains the following result.

Theorem 2. The modified ternary form reduction method reduces a ternary form of size s in O(M(s) log^{2} s) bit-operations.

Proof. Lagarias proves that the sizes of the intermediate ternary forms are O(s). We have seen that the number of iterations is O(log s). One iteration requires O(M(s) log s) bit-operations if one uses the fast reduction for binary forms. ⊓ ⊔

4 From Quasi-Reduced to Reduced

A quasi-reduced form (or a form which is reduced in the sense of Gauß) is not necessarily reduced. For example, the form F given by

M_{F} = (\begin{matrix}4x & 2x & 0 \\ 2x & x + 1 & 0 \\ 0 & 0 & 2x^{2} \end{matrix}) , M_{F^{∗}} = (\begin{matrix}2x^{3} + 2x^{2} & −4x^{2} & 0 \\ −4x^{2} & 8x^{3} & 0 \\ 0 & 0 & 4x \end{matrix})

7:01 7:02 7:03 7:04 7:05 7:06

7:07 7:08

7:09

7:10

7:11

7:12

7:13 7:14

7:15

7:16

7:17

7:18

7:19

7:20

7:21 7:22 7:23

7:24

7:25

7:26

7:27 7:28

7:29 7:30

with Δ_{F} = 8x^{3} is quasi-reduced, but it is far from being reduced, for x → ∞.

In this section we show that we can compute a \frac{16}{3}-reduction of a quasi-reduced ternary form F with O(M(s) log s) bit-operations.

The following lemma states that, if F has two small entries on the diagonal which belong to an associated reduced binary form, then the Gram-Schmidt normalization of F is reduced.

Lemma 1. Let F be a ternary form such that f_{12} is reduced and a_{11}, a_{22} ≤ κ \sqrt[3]{Δ_{F}} for some κ. Then one has

a′_{11}a′_{22}a′_{33} ≤ (\frac{4}{3} + \frac{1}{2}κ^{3}) Δ_{F} ,

for the Gram-Schmidt normalization F′ of F.

Proof. Let

(\begin{matrix}a_{11} & a_{12} & a_{13} \\ a_{12} & a_{22} & a_{23} \\ a_{13} & a_{23} & a_{33} \end{matrix}) = (\begin{matrix}1 & 0 & 0 \\ r_{12} & 1 & 0 \\ r_{13} & r_{23} & 1 \end{matrix}) (\begin{matrix}d_{1} & 0 & 0 \\ 0 & d_{2} & 0 \\ 0 & 0 & d_{3} \end{matrix}) (\begin{matrix}1 & r_{12} & r_{13} \\ 0 & 1 & r_{23} \\ 0 & 0 & 1 \end{matrix})

be the R^{T}DR factorization of the coefficient matrix of F. Since Δ_{f_{12}} = d_{1}d_{2}, f_{12} is reduced, and d_{1} = a_{11}, it follows that

d_{2} ≥ \frac{3}{4} a_{22}.  (16)

Now Δ_{F} = d_{1}d_{2}d_{3} and (16) imply

d_{3} ≤ \frac{4}{3} \frac{Δ_{F}}{a_{11} a_{22}} .  (17)

Let F′ = R′^{T}DR′ be the Gram-Schmidt normalization of F, then

a′_{33} = d_{3} + (r′_{23})^{2} d_{2} + (r′_{13})^{2} d_{1} ≤ d_{3} + (r′_{23})^{2} a_{22} + (r′_{13})^{2} a_{11}
≤ d_{3} + \frac{1}{2}κ \sqrt[3]{Δ_{F}} .  (18)

Since f_{12} is reduced we have not only a′_{11} = a_{11} but also a′_{22} = a_{22} since |r_{12}| ≤ \frac{1}{2}. By combining (17) and (18) and the assumption that a_{11}, a_{22} ≤ κ \sqrt[3]{Δ_{F}}, one obtains

a′_{11} a′_{22} a′_{33} = a_{11} a_{22} a′_{33}
≤ a_{11} a_{22} (d_{3} + \frac{1}{2}κ \sqrt[3]{Δ_{F}})
≤ \frac{4}{3}Δ_{F} + \frac{1}{2}κ^{3} Δ_{F} = (\frac{4}{3} + \frac{1}{2}κ^{3}) Δ_{F} .

Now we are ready to prove that, given a quasi-reduced ternary form F, an equivalent γ-reduction is readily available, for γ = \frac{16}{3}.

Proposition 1. Given a quasi-reduced ternary form F of size s, one can compute with O(M(s) log s) bit-operations a \frac{16}{3}-reduction G of F.

8:01 8:02 8:03

8:04

8:05 8:06 8:07 8:08 8:09 8:10 8:11 8:12 8:13 8:14

8:15 8:16

8:17

8:18

8:19 8:20

8:21 8:22 8:23

8:24

8:25 8:26

8:27

8:28

8:29 8:30

8:31

8:32 8:33 8:34

Proof. Let F be quasi-reduced and let F^{∗} be the adjoint of F. First reduce f_{32}^{∗} in F. This leaves a_{11} unchanged and maybe decreases A_{33}. Recall that a_{11} ≤ 2 \sqrt[3]{Δ_{F}}. It follows from (4) that

\frac{3}{4}A_{33} A_{22} ≤ det f_{32}^{∗} = a_{11}Δ_{F} .  (19)

We normalize f_{12} in F. This leaves the form f_{13} unchanged. Also normalizing f_{13} in F leaves f_{12} unchanged. Therefore normalizing f_{12} and f_{13} in F leaves A_{33} = Δ_{f_{12}} and A_{22} = Δ_{f_{13}} unchanged. If, after these normalizations, f_{12} or f_{13} is not reduced, (2) must be violated and we have two diagonal elements of value at most 2 \sqrt[3]{Δ}. By one more binary form reduction step performed on f_{12} or f_{13} in F, we are in the situation of Lemma 1 with κ = 2 after swapping the second and third row and column if necessary. It is clear that the computations in the proof of Lemma 1 can be carried out in O(M(s)) bit operations. In this case we compute a γ-reduction of F with γ ≤ \frac{4}{3} + 4 = \frac{16}{3}.

If f_{12} and f_{13} are reduced then (4) implies

A_{33} = det f_{12} ≥ \frac{3}{4}a_{11}a_{22}
A_{22} = det f_{13} ≥ \frac{3}{4}a_{11}a_{33}

We conclude from (19) that

a_{11}Δ_{F} ≥ (\frac{3}{4})^{3} a_{11}^{2} a_{22} a_{33}

and thus that

Δ_{F} ≥ (\frac{3}{4})^{3} a_{11} a_{22} a_{33} ≥ \frac{3}{16} a_{11} a_{22} a_{33},

and we have a \frac{16}{3}-reduction of F. The overall amount of bit operations is O(M(s) log s), where the factor log s is required for the binary reduction steps that may be necessary. ⊓ ⊔

By combining Theorem 2 and Proposition 1 we have our main result.

Theorem 3. Given an integral positive definite ternary form F of size s, one can compute with O(M(s) log^{2} s) bit-operations a \frac{16}{3}-reduction of F. ⊓ ⊔

5 Finding the Minimum of a Ternary Form

The following theorem is well known.

Theorem 4. If F is a form in d variables with coefficient matrix M_{F} = (a_{ij}) such that ∏_{i=1}^{d} a_{ii} ≤ γ Δ_{F}, then

λ(F) = min\{ F (x_{1}, …, x_{d}) | |x_{i}| ≤ \sqrt{γ} , x_{i} ∈ ℤ, i = 1, … d \}.  ⊓ ⊔

If the dimension is fixed and F is reduced, then Theorem 4 states that λ(F) can be quickly computed from a constant number of candidates. This gives rise to the next theorem.

9:01 9:02 9:03

9:04 9:05

9:06

9:07

9:08

9:09 9:10 9:11 9:12 9:13 9:14 9:15 9:16 9:17 9:18

9:19

9:20 9:21 9:22 9:23

9:24

9:25 9:26 9:27 9:28 9:29

9:30

9:31 9:32 9:33 9:34

Theorem 5. The minimum λ(F) of a positive definite integral ternary form F of binary encoding length s can be computed with O(M(s) log^{2} s) bit-operations, where M(s) is the bit-complexity of s-bit integer multiplication.

Proof. Given a ternary form F of size s, we first compute a \frac{16}{3}-reduction G of F. Now λ(F) = λ(G) and by Theorem 4, the minimum of G is attained at an

integral vector x ∈ ℤ^{3} with |x_{i}| ≤ \sqrt{\frac{16}{3}}, i = 1, …, 3. By Theorem 3, all this can

be done with O(M(s) log^{2} s) bit-operations. ⊓ ⊔

6 Fast Reduction in any Fixed Dimension

In this section we sketch how the previous technique can be generalized to any fixed dimension. It is more convenient to describe this in the language of lattices. For this we review some terminology. A (rational) lattice Λ ⊆ ℚ^{d} is a set of the form Λ = Λ(A) = {Ax | x ∈ ℤ^{k}}, where A ∈ ℚ^{d×k} is a rational matrix of full column rank. The matrix A is a basis of the lattice Λ and its columns are the basis vectors. The lattice Λ is integral if A ∈ ℤ^{d×k}. The number k is the dimension of the lattice. If k = d, then Λ is full-dimensional. Let F be the quadratic form with coefficient matrix A^{T}A. The lattice determinant of Λ is the number det Λ = \sqrt{Δ_{F}} and the lattice basis A = (x_{1}, …, x_{k}) is reduced if the form F is reduced. More explicitly, this means that

∏_{i=1}^{k} ∥x_{i}∥ ≤ γ det Λ  (20)

for some constant γ. The Lattice Reduction Problem is the problem of computing a reduced basis for a given lattice.

The dual lattice of a full-dimensional lattice Λ is the lattice Λ^{∗} = { y ∈ ℚ^{d} | y^{T}x ∈ ℤ, ∀x ∈ Λ }. Clearly Λ^{∗} = Λ(A^{T}^{−1}) and det Λ^{∗} = 1/ det Λ.

6.1 Lattice Reduction, Shortest Vectors, and Short Vectors

The Shortest Vector Problem is the problem of finding a shortest nonzero vector of a given lattice. This is just the translation of Problem 1 into lattice terminology. Hermite [6] proved that a d-dimensional lattice Λ always contains a (shortest) vector x with ∥x∥ ≤ (4/3)^{(d−1)/4}(det Λ)^{1/d}. We call the problem of computing a vector x with

∥x∥ ≤ κ · (det Λ)^{1/d},

where κ is an arbitrary constant, the SHORT Vector Problem.

Clearly, every shortest vector is also a short vector. If a reduced lattice basis is available, a shortest vector can be computed fast, as mentioned above in Sect. 5 (Theorem 4). The availability of a reduced lattice bases also implies an easy

10:01 10:02 10:03 10:04 10:05 10:06 10:07 10:08

10:09

10:10 10:11 10:12 10:13 10:14 10:15

10:16

10:17 10:18

10:19

10:20 10:21 10:22 10:23

10:24

10:25

10:26

10:27

10:28

10:29 10:30 10:31

10:32

solution of the Short Vector Problem, either directly by (20) or via the Shortest Vector Problem.

So, the Short Vector Problem is apparently the easiest problem among the three problems Lattice Reduction, Shortest Vector, and Short Vector. We will show in Sect. 6.3 that Lattice Reduction (and hence the Shortest Vector Problem) can be reduced to Short Vector. In Sect. 6.2, we will first describe a solution of the Short Vector Problem which proceeds by induction on the dimension, analogously to the procedure of Sect. 3.

6.2 Finding a Short Vector

First we describe how one can find a lattice vector x ∈ Λ of a d-dimensional integral lattice Λ ⊆ ℤ^{d} with ∥x∥ ≤ α (4/3)^{(d−1)/4} \sqrt[d]{det Λ}, for any constant α > 1. The procedure mimics the proof of Hermite [6] who showed that such a vector (with α = 1) exists, see also [12, p. 79].

The idea is to compute a sequence of lattice vectors x_{0}, x_{1}, x_{2}, … which satisfy the relation

∥x_{i+1}∥ ≤ (κ_{d−1})^{d/(d−1)}(det Λ)^{(d−2)/(d−1)^{2}}∥x_{i}∥^{1/(d−1)^{2}},  (21)

for a certain constant κ_{d−1}. This is the generalization of (14) to higher dimensions. We rewrite (21) as

\frac{∥x_{i+1}∥}{(κ_{d−1})^{(d−1)/(d−2)} \sqrt[d]{det Λ}} ≤ [\frac{∥x_{i}∥}{(κ_{d−1})^{(d−1)/(d−2)} \sqrt[d]{det Λ}}]^{1/(d−1)^{2}} .

Arguing as in Sect. 3, we can obtain ∥x_{i}∥ ≤ κ_{d} · (det Λ)^{1/d} in i = O(log log ∥x_{0}∥) steps, if we choose the constant κ_{d} > (κ_{d−1})^{(d−1)/(d−2)}.

We now describe how the successor of x_{i} is computed. Let x_{i} be given. Consider the (d − 1)-dimensional sub-lattice Ω^{∗} of Λ^{∗} defined by

Ω^{∗} = { y ∈ Λ^{∗} | y^{T}x_{i} = 0 }.

The lattice Ω^{∗} has determinant

det Ω^{∗} ≤ ∥x_{i}∥ det Λ^{∗} = ∥x_{i}∥ (det Λ)^{−1}.

We find a short vector ỹ in Ω^{∗} with

∥ỹ∥ ≤ κ_{d−1}(∥x_{i}∥ (det Λ)^{−1})^{1/(d−1)}.

This is a Short Vector Problem in d − 1 dimensions, which is solved inductively. Now we repeat the same procedure, going from the dual lattice back to the original lattice: consider the (d − 1)-dimensional sub-lattice Γ of Λ defined by

Γ = { x ∈ Λ | ỹ^{T}x = 0 },

11:01

11:02

11:03 11:04 11:05 11:06

11:07 11:08 11:09 11:10

11:11 11:12 11:13

11:14

11:15 11:16

11:17 11:18 11:19 11:20 11:21 11:22 11:23 11:24 11:25 11:26

11:27 11:28 11:29

11:30 11:31 11:32

11:33

11:34 11:35 11:36 11:37 11:38

whose determinant satisfies

det Γ ≤ ∥ỹ∥ · det Λ ≤ κ_{d−1}(det Λ)^{(d−2)/(d−1)}∥x_{i}∥^{1/(d−1)}.

We find a short vector x_{i+1} of Γ with ∥x_{i+1}∥ ≤ κ_{d−1} (det Γ)^{1/(d−1)}, which immediately yields (21). ⊓ ⊔

As a consequence one obtains the following proposition which generalizes Theorem 2.

Proposition 2. Let d ∈ ℕ, d ≥ 3, and let κ_{d−1} be some constant. Suppose that, in an integral lattice Γ of dimension d − 1 with binary encoding length s, a short vector x with

∥x∥ ≤ κ_{d−1} (det Γ)^{1/(d−1)}

can be found in T_{d−1}(s) bit-operations. Then, for an integral lattice basis A ∈ ℤ^{d×d} with binary encoding length s, we can compute a basis B ∈ ℤ^{d×d} of the generated lattice Λ such that the first column vector x of B satisfies

∥x∥ ≤ κ_{d} (det Λ)^{1/d},

in T_{d}(s) = O(T_{d−1}(s) log s + M(s) log s) bit-operations, for any constant κ_{d} with κ_{d} > (κ_{d−1})^{(d−1)/(d−2)}.

Proof. We start the sequence x_{0}, …, x_{k} with an arbitrary vector x_{0} out of the basis A. The successors are computed as described above. The computation of ỹ can be done with O(T_{d−1}(s) + M(s)) bit-operations, since this involves only one (d − 1)-dimensional shortest vector problem and basic linear algebra. The same time bound holds for the computation of x_{i+1}. These computations have to be repeated at most O(log log ∥x_{0}∥) times and we arrive at a lattice vector x with ∥x∥ ≤ κ_{d} (det Λ)^{1/d}. Now we determine an integral vector y ∈ ℤ^{d} with Ay = x. With the extended Euclidean algorithm one can find a unimodular matrix U ∈ ℤ^{d×d} with first column y/ gcd(y_{1}, …, y_{d}). The matrix B = AU is as claimed. ⊓ ⊔

We can use this proposition inductively, starting with κ_{2} = \sqrt[4]{4/3} and T_{2}(s) = O(M(s) log s). We see that we can choose κ_{d} as close to (4/3)^{(d−1)/4} as we like. So we obtain:

Corollary 1. In a d-dimensional integral lattice Λ ⊆ ℤ^{d}, a lattice vector x with ∥x∥ ≤ κ\sqrt[d]{det Λ} can be found in O(M(s) log^{d−1} s) time, for any constant κ > (\frac{4}{3})^{(d−1)/4}. ⊓ ⊔

6.3 Augmenting the Number of Short Vectors in the Basis

Now we generalize the approach of Sect. 4 to get a reduced basis. Suppose we have a basis v_{1}, …, v_{d} of the d-dimensional lattice Λ which is not reduced and such that the first k ≥ 1 basis vectors satisfy ∥v_{i}∥ ≤ α\sqrt[d]{det Λ}, 1 ≤ i ≤ k for some constant α depending on d and k only. We describe a procedure that computes a new basis v′_{1}, …, v′_{d} which satisfies one of the following.

12:01 12:02 12:03

12:04 12:05 12:06 12:07 12:08 12:09

12:10 12:11 12:12 12:13

12:14

12:15

12:16

12:17

12:18

12:19 12:20

12:21

12:22

12:23 12:24

12:25

12:26 12:27 12:28 12:29 12:30 12:31 12:32 12:33

(a) v′_{1}, …, v′_{d} is reduced, or

(b) for all 1 ≤ j ≤ k + 1 one has v′_{j} ≤ α^{∗} \sqrt[d]{det Λ} for some constant α^{∗} depending on d and k + 1 only.

Let L be the subspace of ℝ^{d} which is generated by the vectors v_{1}, …, v_{k} and denote its orthogonal complement by L^{⊥}. Let v̄_{j} denote the projection of v_{j} into L^{⊥}. Let Λ^{(1)} be the k-dimensional lattice generated by v_{1}, …, v_{k} and let Λ^{(2)} be the (d − k)-dimensional lattice generated by the vectors v̄_{k+1}, …, v̄_{d}. Clearly det Λ^{(1)} det Λ^{(2)} = det Λ. Let

ū_{k+1}, …, ū_{d}

be a reduced basis of Λ^{(2)} and suppose that ū_{k+1} is the shortest among these basis vectors. Let U ∈ ℤ^{(d−k)×(d−k)} denote the unimodular matrix which transforms (v̄_{k+1}, …, v̄_{d}) into (ū_{k+1}, …, ū_{d}). The vectors v_{j}^{∗} ∈ Λ defined by (v_{k+1}^{∗}, …, v_{d}^{∗}) = (v_{k+1}, …, v_{d}) U are of the form

v_{j}^{∗} = ū_{j} + ∑_{i=1}^{k} μ_{ij} v_{i},

with some real coefficients μ_{ij}. It follows that

v′_{j} = ū_{k+1} + ∑_{i=1}^{k}{μ_{ij}} v_{i} ∈ Λ,

where {x} denotes the fractional part of x. Clearly

v_{1}, …, v_{k}, v′_{k+1}, …, v′_{d}

is a basis of Λ and

∥v′_{j}∥ ≤ ∥ū_{j}∥ + kα\sqrt[d]{det Λ}.

There are two cases. If ∥ū_{k+1}∥ > \sqrt[d]{det Λ}, then for all j = k + 1, …, d,

∥v′_{j}∥ ≤ (kα + 1) ∥ū_{j}∥.

Thus we get ∥v′_{k+1}∥ ⋯ ∥v′_{d}∥ ≤ α_{2} det Λ^{(2)} for some constant α_{2} since ū_{k+1}, …, ū_{d} is reduced. Now let v′_{1}, …, v′_{k} be a reduced basis of Λ^{(1)}. Then

∥v′_{1}∥ ⋯ ∥v′_{d}∥ ≤ α_{1} det Λ^{(1)} α_{2} det Λ^{(2)} = α_{1} α_{2} det Λ,

which means that v′_{1}, …, v′_{d} is reduced and thus (a) holds.

If, on the other hand, ∥ū_{k+1}∥ ≤ \sqrt[d]{det Λ}, then the basis v_{1}, …, v_{k}, v′_{k+1}, …, v′_{d} satisfies (b). ⊓ ⊔

Now it is clear how to proceed. We find the first short basis vector by Proposition 2, and we iterate the above procedure as long as case (b) prevails, increasing k. We must eventually end up with a reduced basis, because as soon as k reaches d, we have ∥v_{i}∥ ≤ α\sqrt[d]{det Λ} for all basis vectors v_{i}, and this implies that the basis is reduced.

13:01 13:02 13:03 13:04 13:05

13:06 13:07 13:08 13:09

13:10

13:11 13:12 13:13 13:14 13:15 13:16 13:17 13:18 13:19 13:20 13:21 13:22 13:23 13:24 13:25 13:26 13:27 13:28 13:29 13:30 13:31 13:32 13:33 13:34 13:35 13:36 13:37 13:38 13:39 13:40 13:41 13:42 13:43 13:44 13:45 13:46 13:47

In this way, we have reduced the Lattice Reduction Problem in dimension d to one d-dimensional Short Vector Problem and a constant number (fewer than 2d) of lower-dimensional lattice reduction problems, plus some linear algebra which can be done in O(M(n)) time. Thus we obtain the following theorem by induction on the dimension.

Theorem 6. Let d ∈ ℕ, d ≥ 2, A ∈ ℤ^{d×d} be a lattice basis generating Λ and suppose that the binary encoding length of A is s. Then one can compute with O(M(s) log^{d−1} s) bit-operations a reduced basis of Λ or a shortest vector of Λ.

⊓ ⊔

References

1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, 1974.

2. J. W. S. Cassels. Rational quadratic forms. Academic Press, 1978.

3. F. Eisenbrand. Short vectors of planar lattices via continued fractions. Information Processing Letters, 2001, to appear. http://www.mpi-sb.mpg.de/~eisen/

report_lattice.ps.gz

4. C. F. Gauß. Disquisitiones arithmeticae. Gerh. Fleischer Iun., 1801.

5. C. F. Gauß. Recension der "‘Untersuchungen über die Eigenschaften der positiven ternären quadratischen Formen von Ludwig August Seeber"’. Reprinted in Journal für die reine und angewandte Mathematik, 20:312–320, 1840.

6. Ch. Hermite. Extraits de lettres de M. Ch. Hermite à M. Jacobi sur différents objets de la théorie des nombres. Journal für die reine und angewandte Mathematik, 40, 1850.

7. J. C. Lagarias. Worst-case complexity bounds for algorithms in the theory of integral quadratic forms. Journal of Algorithms, 1:142–186, 1980.

8. A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Math. Annalen, 261:515–534, 1982.

9. H. W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538–548, 1983.

10. A. Schönhage. Fast reduction and composition of binary quadratic forms. In International Symposium on Symbolic and Algebraic Computation, ISSAC 91, pages 128–133. ACM Press, 1991.

11. A. Schönhage and V. Strassen. Schnelle Multiplikation grosser Zahlen (Fast multiplication of large numbers). Computing, 7:281–292, 1971.

12. A. Schrijver. Theory of Linear and Integer Programming. John Wiley, 1986.

13. L. A. Seeber. Untersuchung über die Eigenschaften der positiven ternären quadratischen Formen. Loeffler, Mannheim, 1831.

14. I. Semaev. A 3-dimensional lattice reduction algorithm. In: J. H. Silverman (ed.), CaLC 2001, Cryptography and Lattices Conference, Lecture Notes in Computer Science, vol. 2146 (this volume), Springer-Verlag, 2001, pp. 181–193.

15. B. Vallée. An affine point of view on minima finding in integer lattices of lower dimensions. In Proceedings of the European Conference on Computer Algebra, EUROCAL ’87, volume 378 of Lecture Notes in Computer Science, pp. 376–378. Springer, Berlin, 1989.

16. C. K. Yap. Fast unimodular reduction: Planar integer lattices. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 437–446, Pittsburgh, 1992. IEEE Computer Society Press.