# Significance of parameter q in NTRU lattice attack

In NTRU (N,p,q,d), N is usually chosen to be prime and q be a power of 2. Why is it that if I increase the parameter q, the probability of finding a key or spurious key that can decrypt the message is much higher?

For example, N=127, q=256 will give me an unsuccessful lattice attack but N=127, q=2^16 will give me a successful lattice attack

Basically, the norm of the secret key does not depend on $$q$$, while the norm of the second minimum of the lattice does, so, when you increase $$q$$, you increase the gap between the first and the second minima of the lattice, which makes the problem easier.
For instance, if the secret key is composed by two degree-$$(N-1)$$ polynomials $$f$$ and $$g$$ with coefficients in $$\{-1, 0, 1\}$$, then we have $$||(f, g)|| < 2N$$.
One basis of the lattice $$L$$ that we use in attack is $$\begin{pmatrix} I_N & H \\ 0 & q\cdot I_N \end{pmatrix} \in \mathbb{Z}^{2N\times 2N}$$ So, it is clear that $$\det(L) = q^N$$ and $$\dim(L) = 2N$$. Then, by the Gaussian Heuristic, we expect the short vectors of $$L$$ to have norm close to $$\sqrt{N}(\det(L))^{1/\dim(L)} = \sqrt{Nq}$$.
Because $$(f, g) \in L$$ and $$||(f, g)||$$ is smaller than the value predicted by the Gaussian Heuristic, there is a "gap" in $$L$$, that is, we expect that $$\lambda_1(L) = ||(f, g)||$$ and $$\lambda_2(L) \approx \sqrt{Nq}$$.
Now, roughly speaking, if the vector that we recovered is shorter than the second shortest vector, then it has to be the first shortest vector. So, when we run a lattice basis reduction, if we recover a vector smaller than $$\sqrt{Nq}$$, it will already be (a short multiple of) $$(f, g)$$ and we win.