Find The Lattice
I did not manage to solve this challenge. The private key is composed by some $f, g$, both smaller than $\sqrt{\frac{q}{2}}$, with the relation that $fh - g = 0 \mod q$ This means that there exists a $k$ such that $fh = qk + g$, since $h$ is about the same size of $q$, we have that $k$ is the same size of $f$. We have the observation that $f \cdot (h, 1) + (-k) \cdot (q, 1) = (g, f - k)$, where both components of the result are small (g is around the square root of $\frac{q}{2}$, and $f$ is approximately $k$)....