Introduction to Cryptography with Coding Theory, 3rd Edition

23.7 Exercises

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

2. 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].)

3. 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.

4. Let $\{v_1\text{,}{v}_2\}$ be ...