# 23.7 Exercises

1. Find a reduced basis and a shortest nonzero vector in the lattice generated by the vectors .

1. Find a reduced basis for the lattice generated by the vectors , .

2. Find the vector in the lattice of part (a) that is closest to the vector . (Remark: This is an example of the closest vector problem. It is fairly easy to solve when a reduced basis is known, but difficult in general. For cryptosystems based on the closest vector problem, see [Nguyen-Stern].)

2. Let  be linearly independent row vectors in . Form the matrix  whose rows are the vectors . Let  be a row by , and show that every vector in the lattice can be written in this way.

3. Let  be a basis of a lattice. Let  be integers with , and let


1. Show that


2. Show that  is also a basis of the lattice.

4. Let  be a positive integer.

1. Show that if , then  is a multiple of .

2. Let . Let  be integers and let



where the sum is over pairs  with . Show that



is a multiple of .

3. Let  and  be polynomials of degree less than . Let  be the usual product of  and  and let  be defined as in Section 23.4. Show that  is a multiple of .

5. Let  and  be positive integers. Suppose that there is a polynomial  such that . Show that . (Hint: Use Exercise 5(c).)

1. In the NTRU cryptosystem, suppose we ignore  and let . Show how an attacker can obtain the message quickly.

2. In the NTRU cryptosystem, suppose  is a multiple of . Show how an attacker can obtain the message quickly.