In NTRUEncrypt, we choose polynomials $\mathbf f,\mathbf g$ (with suitably small coefficients) such that $\mathbf f$ admits inverses $\mathbf f_p, \mathbf f_q$ with respect to the moduli $p,q$. The relationship between the public $\mathbf h=\mathbf f_q\mathbf g\text{ mod q}$ and the private key $(\mathbf f, \mathbf f_p)$ is used to define a lattice
\begin{equation} \mathcal L=\{(\mathbf u,\mathbf v)\in \mathbf T\times \mathbf T\text{ t.c. } \mathbf u\mathbf h\equiv \mathbf v\mod q\}\subset \mathbb Z^{2N}. \end{equation}
From $\mathbf h\equiv \mathbf{f}_q\mathbf g\text{ mod } q$ it follows that $\mathbf f\mathbf h\equiv \mathbf g\text{ mod } q$, therefore $(\mathbf{f},\mathbf g)\in \mathcal L$. The same expression can be written as \begin{equation} \mathbf{fh-u}q=\mathbf g, \quad \mathbf u \in \mathbf T, \end{equation}
which becomes in matrix form \begin{equation} \begin{pmatrix} \mathbf f \\ \mathbf g \end{pmatrix}=\begin{pmatrix} 1 & 0 \\ \mathbf h & q \end{pmatrix}\begin{pmatrix} \mathbf f \\ - \mathbf u \end{pmatrix} \end{equation} and using the coordinates of the polynomials \begin{equation*}\scriptsize{ \begin{pmatrix} f_0 \\ f_1 \\ \vdots \\ f_{N-1} \\ g_0 \\ g_1 \\ \vdots \\ g_{N-1} \end{pmatrix} = \left(\begin{array}{@{}cccc|cccc@{}} 1 & 0 & \cdots & 0 & 0 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & 0 & 0 & \cdots & 0 \\ \hline h_0 & h_1 & \cdots & h_{N-1} & q & 0 & \cdots & 0 \\ h_{N-1} & h_0 & \cdots & h_{N-2} & 0 & q & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ h_1 & h_2 &\cdots & h_0 & 0 & 0 & \cdots & q \end{array}\right) \begin{pmatrix} f_0 \\ f_1 \\ \vdots \\ f_{N-1} \\ -u_1 \\ -u_2 \\ \vdots \\ -u_{N-1} \end{pmatrix}. } \end{equation*} Why do we need in this expansion the circulant matrix of all cyclic shifts of $\mathbf h$?
