Choosing $x^n+1$ as an irreducible polynomial in $\mathbb{Z}[x]$ instead of $x^n-1$ for ring $\mathbb{Z}[x]/\langle f(x)\rangle$ of Ring-LWE

Question

In the note of ["Ring-SIS and Ideal Lattices by Noah Stephens-Davidowitz (for Vinod Vaikuntanathan’s class", footnote 3], it has written:

---

3 The ring $\mathbb{Z}[x]/(x^n + 1)$, ideal lattices, and a secure collision-resistant hash function

Recall that our attack on $h_a$ over $\mathbb{Z}[x]/(x^n - 1)$ relied on the fact that $x^n - 1$ has a nontrivial factor over the integers, $x^n - 1 = (x - 1)(x^{n-1} + x^{n-2} + \cdots + 1)$. So, it is natural to try replacing $x^n - 1$ with an irreducible polynomial. Indeed, one can easily show that $\mathbb{Z}[x]/(p(x))$ for some polynomial $p(x) \in \mathbb{Z}[x]$ is an integral domain if and only if $p$ is irreducible.

We strongly prefer sparse polynomials with small coefficients (both because they are easy to work with and because this ensures that our ring has nice "geometric" properties). Since $x^n - 1$ failed, we try $x^n + 1$. This is irreducible over $\mathbb{Z}$ if and only if $n$ is a power of two. ...

---

If $p > 1$ is a non-trivial odd factor of $n$, then $x^{\frac{n}{p}} + 1$ is a non-trivial factor of $x^n + 1$.

If $n$ has no odd factors, then $x^n + 1$ is the $2n$th cyclotomic polynomial-i.e., the minimal polynomial over $\mathbb{Z}$ of any primitive $2n$th root of unity.

I know a little about cyclotomic polynomials. Can someone explain or refer me to a reference for these arguments.

How to reach to the first point? Why it says $2n$th cyclotomic polynomial and not $n$th one?

Answer 1

If $p>1$ is a non-trivial odd factor of $n$, then $x^{n/p}+1$ is a non-trivial factor of $x^n+1$.

Any root $r$ of $x^{n/p}+1$ satisfies $r^{n/p} = -1$. For such a root, we have that $$r^n+1 = (r^{n/p})^p + 1 = (-1)^p + 1 = 0,$$ as $p$ is odd. You probably need an argument that all of the roots of $x^{n/p}+1$ are simple as well (they are). I'll leave you to figure this out though.

If $n$ has no odd factors, then $x^n+1$ is the $2n$th cyclotomic polynomial-i.e., the minimal polynomial over $\mathbb{Z}$ of any primitive $2n$th root of unity.

Recall the definition of a cyclotomic polynomial.

The $n$th cyclotomic polynomial $\Phi_n(x)$ is the unique irreducible polynomial with integer coefficients that is a divisor of $x^n-1$ and is not a divisor of $x^k-1$ for any $k<n$.

So, $x^n+1$ is a divisor of $x^{\color{red}{2n}}-1 = (x^n+1)(x^n-1)$, hence we call it the ${\color{red}{2n}}$th cyclotomic polynomial. Note that the $n$th cyclotomic polynomial is never degree $n$. It is instead degree $\varphi(n)$, where $\varphi$ is Euler's totient function. You can also see that

$$ x^{2n}-1 = (x^n+1)(x^n-1) = \Phi_{2n}(x)(x^n-1). $$ It seems quite likely that $x^n-1$ factors further (it is at least divisible by $x-1$). This hints at the more general relationship

$$ x^n-1 = \prod_{d\mid n}\Phi_d(x), $$ true for any $n\in\mathbb{N}$.