Copyright
Bud Mishra.

Lecture notes in lattices, bases and the reduction problem (expository notes) online

. (page 1 of 2)
Online LibraryBud MishraLecture notes in lattices, bases and the reduction problem (expository notes) → online text (page 1 of 2)
Font size
QR-code for this ebook


Robotics Research
lechnical Report




'"'"''« ta6,














^iM^lii






Lecture Notes on Lattices, Bases

and the Reduction Problem

(Expository Notes)

by

Bud Mishra



Technical Report No. 300

Robotics Report No. 113

June, 1987




\,



New York University
nt Institute of Mathematical Sciences

Computer Science Division

25 1 Mercer Street New York, NX 1 00 1 2




Lecture Notes on Lattices, Bases

and the Reduction Problem

(Expository Notes)

by

Bud Mishra



Technical Report No. 300

Robotics Report No. 113

June, 1987



New York University

Dept. of Computer Science

Courant Institute of Mathematical Sciences

251 Mercer Street

New York, New York 10012



Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-
0381, National Science Foundation CER Grant DCR-83-20085, and by grants from the Digi-
tal Equipment Corporation and the IBM Corporation.



Abstract

These sets of notes are somewhat fleshed out version of the Sec-
tion 1.2. of Lovasz's Book "An Algorithmic Theory of Numbers,
Graphs and Convexity.'" Both Cassel's and Lekkerkerker's books
are excellent texts on Geometry of Numbers. However, we need
only a small portion of these books, and we develop the materials
ab initio.



Lattices, Bases and the Reduction Problem



1 Geometry of Numbers

The subject of ^''geometry of numbers^ was developed by Minkowski around
the turn of the century. This has been a classical tool in subjects such as
integral quadratic forms , diophantine approximations. However, it occupied
its renewed role as a powerful tool in Computer Science, after H.W. Lenstra
used it to give a polynomial time algorithm for the Integer Programming
(Feasibility) Problem for fixed number of variables. Since then it has been
used to give efficient algorithms in as diverse areas as simultaneous diophan-
tine approximations, cryptography, solvability by radicals, low density subset
sum problem, computing with algebraic numbers, factorization of polynomi-
als over finite fields.

The main approach common to all the algorithms involves reformulating
the initial problem as a geometrical problem concerning lattices of points.
The geometric insights gained by such representations is a powerful aid to
thinking about both classical and algorithmic problems.

Definition 1.1 [Lattice]

Let ci, a2, . . ., On G IR" be a set of linearly independent vectors in IR". Let

A be an n X n matrix with columns oi, 02, . . ., a„,

A - {ai,a2,...,an).

The lattice generated by A {by ai, a2, . ■ ., a^) is defined to be

A = A{A) = 7Lai + 7La2 + - - + TLa^ = {AjCi + AjCj + • • • A„a„ | A, G ZZ},

i.e., integer linear combinations of the vectors gi, 02, . . ., a^.

We say that ax, a^, . . ., a^ is a basis of the lattice A(ai, 02, . . . ,a„), and
A is its basis matrix. We say n is the dimension of the lattice A. D

The same lattice A may have many bases, but they are related to one
another.

Definition 1.2 A square matrix U is called unimodular, if

dett/ = ±l. D

Theorem 1.1 Let Ai = A(Ai) and A2 = A(/l2) be two n-dimensional lat-
tices, with basis matrices Ai and A2, respectively. Then Ai = A2, if and
only if there exists an integer unimodular matrix U, such that

Ai = A2U.



Section 1 Geometry of Numbers



PROOF.

{=>) Assume Aj = A2. Then the column vectors of A2 are integer linear
combinations of the column vectors of Ai, and vice versa. Hence there are
integer matrices Ui and U2 such that

A2 — A\Ui, and Ai = A2U2-

Hence

A^ = AiUiU2.

Since A\ is of full rank,

where /„ is the n X n identity matrix. This implies

det Ui det C/2 = 1 , and det Ui , det U2 G Z;
from which we conclude that

|detC/i| = 1 = |detf/2|.

The matrices U\ and U2 are integer unimodular matrices.

( j-



Lattices, Bases and the Reduction Problem



Hence,

B = B'M'^,

where Af is an n X n lower triangular matrix with the (i, j)*^ entry,
fiij, and B and B* are the nxn matrices with the column vectors 6,'s
and 6*'s, respectively. Note that

detB'^B = det MiB')'^B'M^ = det{B'fB',

since

n

detJW = Y[fii,i = 1.

(B) Since the column vectors of B* are mutually orthogonal,

{B')^B' = diag {{6-, 6-)}, = diag {||6n|'}^,

and

det iB'fB' = f[\\b:\\\

(C) From (A), we know that

Since 6*'s are mutually orthogonal.

Hence we obtain the following inequality, known as Hadamard's In-
equality:



detB^B = deiiB*fB' = JJ ||6*|p < J] ll^ll'-

i=i t=i

Equivalently,

|detB|. 0, let ^S stand for the following centrally symmetric
convex body

^s = Ux\xe s).

Let A be an n-dimensional lattice in IR". The quantity

^k = iiif{^ > I ^5 contains k linearly independent vectors from A}

is called the k*'^ successive minimum of A with respect to S (for k = 1, . . .,
n).

The set of successive minima {^^ | A; = 1, ..., n} exist and there are
n linearly independent vectors b\, 62, ..., b^ in A, corresponding to the
successive minima.

Furthermore

6 < 6 < • • • < ^n. □

By Minkowski's Convex Body Theorem it follows that (fi5 has a volume

F(^i5) = ,fi"F(*^) ^n (associated
with the successive minima) have the following additional property:

\M = ^k.

Note that although 61, 62, • . •, &n are vectors of the lattice A, and are linearly
independent, they may not form a basis of the lattice. However the following
lemma shows that there is a basis (ai, 02, .. ., o-n) of A that is 'quite close'
to the set of vectors {61, 62, . . ., 6„}.

Lemma 4.2 Let 61, 62, . .., bn be the n linearly independent vectors associ-
ated with the successive minima of the n-dimensional lattice A. Then there
exists a basis (oj, 02, ..., On) of A such that



||a,|| 7n ■v/detT then such a vector 6 always exists;
here, 7„ > v/ ^- Note, however, that a lattice A may contain a vector
much shorter than {/det A.

Let 7„ = ||6||/ vdetA denote the smjJIest constant satisfying the above
inequality. It is known that



n

:r- < 7n < „ .
Jex V e'K

It is widely believed that the Short Vector Problem (and hence the
related search problem: Shortest Vector Problem) is A'^P-complete,
though no such proof is currently available. It is not knowTi either
whether the weaker problem of finding a solution if ^ = a/tT v^det A is
A' P- hard.

The above discussion indicates that the best we may hope for is a poly-
nomial time algorithm to find a 'reduced basis.' In the rest of this chap-
ter, we present Lenstra, Lenstra and Lovasz's Basis Reduction Algorithm
[Lenstra et. al. 1982] that finds a basis (6i, 62, . . ., 6„) of a lattice A satisfy-
ing the following inequality:

ll^ill 11^211 •••||6n||
bn) via a sequence of unimodular integer transformations such that

t

where



ro, ifi i) or (A; = t A / > j).

Now, let m = [Mm] be the integer nearest to Jiij. Consider the following
new basis of A, (6j, . . ., b'-, . . ., b'^) = (6i, . . ., 6, — m • 6j, . . ., 6„), obtained
by an integer unimodnlar transformation



b[ = 6i



bl



b[ = bi — m ■ bj

= (mu - m- lJ~})bl + ■■■+ {p~~ - m)b' + /^^Tfi^j+i + ■•• + &*

= /aTi^i + • • • + M^r^i^^-i + i^

Now, let {i\j') be the lexicographically largest pair of indices satisfying the
following conditions:

\^^,',J'\ > 2'^"^

\^^'k,l\ ^ 9' f°^ ^1^ ^^^ s"ch that (A: > t') or [k = i' A I > j').

It is easy to see that

(«',/) • • •> ^n) and {b[, 65, . . ., 6'„) have the
same Gram-Schmidt orthogonal! zation: (6J, 621 - m ^n)-

Hence by repeating above step at most {T} many times, it is possible
to obtain a weakly reduced basis (61, 62, •••> ''n)i starting from the original
basis (61, 621 • • •-, bn)- The following algorithm achieves this:



20



Lattices, Bases and the Reduction Problem


1

Online LibraryBud MishraLecture notes in lattices, bases and the reduction problem (expository notes) → online text (page 1 of 2)