Find a reduced basis and a shortest nonzero vector in the lattice generated by the vectors $(58\text{,}19)\text{,}(168\text{,}55)$.

1. Find a reduced basis for the lattice generated by the vectors $(53\text{,}88)$, $(107\text{,}205)$.

2. Find the vector in the lattice of part (a) that is closest to the vector $(151\text{,}33)$. (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 $v_1\text{,}\dots \text{,}{v}_n$ be linearly independent row vectors in ${\mathbf{R}}^n$. Form the matrix $M$ whose rows are the vectors $v_i$. Let $\bar{a}=(a_1\text{,}\dots \text{,}{a}_n)$ be a row by $v_1\text{,}\dots \text{,}{v}_n$, and show that every vector in the lattice can be written in this way.

Let $\{v_1\text{,}{v}_2\}$ be a basis of a lattice. Let $a\text{,}b\text{,}c\text{,}d$ be integers with $ad-bc=\pm 1$, and let

1. Show that

   $v_1=\pm (d{w}_1-b{w}_2)\text{,}{v}_2=\pm (-c{w}_1+a{w}_2)\text{.}$

2. Show that $\{w_1\text{,}{w}_2\}$ is also a basis of the lattice.

Let $N$ be a positive integer.

1. Show that if $j+k\equiv i(\text{mod}N)$, then $X^{j+k}-X^i$ is a multiple of $X^N-1$.

2. Let $0\le i<N$. Let $a_0\text{,}\dots \text{,}{a}_{N-1}\text{,}{b}_0\text{,}\dots \text{,}{b}_{N-1}$ be integers and let

   $$c_i=\sum _{j+k\equiv i}{a}_j{b}_k\text{,}$$

   where the sum is over pairs $j\text{,}k$ with $j+k\equiv i(\text{mod}N)$. Show that

   $$c_i{X}^i-\sum _{j+k\equiv i}{a}_j{b}_k{X}^{j+k}$$

   is a multiple of $X^N-1$.

3. Let $f$ and $g$ be polynomials of degree less than $N$. Let $fg$ be the usual product of $f$ and $g$ and let $f\ast g$ be defined as in Section 23.4. Show that $fg-f\ast g$ is a multiple of $X^N-1$.

Let $N$ and $p$ be positive integers. Suppose that there is a polynomial $F(X)$ such that $f(X)\ast F(X)\equiv 1(\text{mod}p)$. Show that $f(1)\cancel{\equiv }0\text{mod}p$. (Hint: Use Exercise 5(c).)

1. In the NTRU cryptosystem, suppose we ignore $q$ and let $c=p\varphi \ast h+m$. Show how an attacker can obtain the message quickly.

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