Find a reduced basis and a shortest nonzero vector in the lattice generated by the vectors .
Find a reduced basis for the lattice generated by the vectors , .
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].)
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.
Let be a basis of a lattice. Let be integers with , and let
Show that is also a basis of the lattice.
Let be a positive integer.
Show that if , then is a multiple of .
Let . Let be integers and let
where the sum is over pairs with . Show that
is a multiple of .
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 .
Let and be positive integers. Suppose that there is a polynomial such that . Show that . (Hint: Use Exercise 5(c).)
In the NTRU cryptosystem, suppose we ignore and let . Show how an attacker can obtain the message quickly.
In the NTRU cryptosystem, suppose is a multiple of . Show how an attacker can obtain the message quickly.