# In NTRU, if $N$ is not prime, prove that one can recover the private key by solving a lattice problem in dimension lower than $2N$

In the NTRU cryptosystem, it is suggested to take $N$ prime. I want to understand why.

In Jeffrey Hoffstein, Jill Pipher and H. Silverman An Introduction to Mathematical Cryptography, they suggest (as exercise) to suppose that $N$ is even, to consider the natural map $$\mathbb{Z}[X]/\langle X^N-1 \rangle \longrightarrow \mathbb{Z}[X]/\langle X^{N/2}-1 \rangle,$$ and prove that one can recover the private key by solving a lattice problem in dimension $N$, rather than in dimension $2N$.

Can someone explain how can we do this, please? Thanks in advance.

• Hint: $X^N-1 = (X^{N/2}+1)(X^{N/2}-1)$. Use this to solve for the key modulo each factor. – Chris Peikert Jul 11 '16 at 4:51
• I have already tried it, I reduce the public key $h$ modulo $X^{N/2}-1$ and consider the associated lattice now of dimension $N$. Similarly, reduce $h$ modulo $X^{N/2}+1$ and do the same thing. Assume that I can find the private key for these two smaller lattices. I don't understand how can I recover the original private key... – Leafar Jul 11 '16 at 10:38
• Use the Chinese Remainder Theorem to combine the two solutions. – Chris Peikert Jul 11 '16 at 11:51
• Right, thanks, how can I generalize for arbitrary composite $N$. For example, take $N=15$. What is the appropriate decomposition of the polynomial $X^{15}-1$? – Leafar Jul 12 '16 at 16:06
• See the beginning of en.m.wikipedia.org/wiki/Cyclotomic_polynomial – Chris Peikert Jul 12 '16 at 16:08