Bud Mishra. # Lecture notes in lattices, bases and the reduction problem (expository notes) online

. **(page 1 of 2)**

Online Library → Bud Mishra → Lecture notes in lattices, bases and the reduction problem (expository notes) → online text (page 1 of 2)

Font size

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

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 2

Online Library → Bud Mishra → Lecture notes in lattices, bases and the reduction problem (expository notes) → online text (page 1 of 2)