How does the polynomial modulus work in the Fan-Vercauteren scheme?

Question

I'm reading this introductory blog on the Fan-Vercauteren scheme and there are a few things I don't understand about polynomial moduli. The author uses practical examples:

Because we are considering remainders with respect to $x^{16}+1$, we only have to consider polynomials with powers from $x^0$ to $x^{15}$. Any larger powers will be reduced by division by the polynomial modulus. This can also be understood by considering that $x^{16}\equiv −1(\mathrm{mod} \ x^{16}+1)$, meaning that $x^{16}$ can be replaced by -1 to reduce the larger powers of x into the range 0 to 15.

I don't understand the third sentence at all, $x^{16} \equiv -1$?

Further down the tutorial, there is a practical example of polynomial multiplication followed by a division by polynomial modulus:

When we multiply two powers of x, say $2x^{14}$ and $x^4$, we add their exponents - making $2x^{18}$. One might assume that finding the remainder of this polynomial with respect to the polynomial modulus might involve just rotating the exponent back through 0 at $x^{16}$, to give $2x^{2}$, like it does for the integer coefficients shown above. This would be the case if the polynomial modulus was just $x^{16}$. However, our polynomial modulus is $x^{16}+1$ - as mentioned above, the extra plus one factor introduces a sign change which helps further scramble the result of the multiplication.

How does this extra plus one factor introduce a sign change?

and finally:

...multiplication of a term $2x^{14}$ by $x^4$ modulo $x^{16}+1$ takes this term (represented by the red dot above), rotates it forward 4 powers around the torus, and then reflects the value across the 0 point, making $22x^2$ (or $−2x^2$ if we consider numbers from -12 to 11 rather than 0 to 23).

$2x^{18}$ modulo $x^{16}+1 = 22x^2$, how?

Answer 1

You have to pay attention to the fact that two moduli are used: a polynomial modulus $x^n + 1$ and an integer modulus $t$ (in that example, $n = 16$ and $t = 24$).

In practice, it means that not only the degree is limited but also the coefficients: they always lie in $\mathbb{Z}_t$, which is traditionally represented as the set $[0, t-1] \cap \mathbb{Z}$, but in lattice-related texts, it is usually represented as $[-t/2, t/2) \cap \mathbb{Z}$.

So, for the first point, it is easy if you think that for any polynomial $p(x)$, reducing it modulo itself results in a zero, i.e., $p(x) \equiv 0 \pmod{ p(x)}$, because the division $p(x) / p(x)$ is $1$ with remainder $0$. Hence, taking $p(x) = x^n+1$ gives us

$$x^n+1 = 0 \pmod{x^n+1} \Rightarrow x^n = -1 \pmod{x^n+1}.$$

Now, if you use the properties of modular multiplication, you will see that when you reduce a polynomial modulo $x^n +1$, you will actually replace the powers $x^n$ by $-1$, $x^{n+1}$ by $-x$, $x^{n+2}$ by $-x^2$, etc.

Thus, for instance, $2x^{14} \cdot x^4 = 2x^{18} = 2x^2 \cdot x^{16}$. But since $x^{16} = -1$ because of the modular reduction, we have

$$2x^{14} \cdot x^4 = -2x^2 \pmod{x^{16}+1}.$$

Until this point, only the polynomial reduction was done, but we also need to compute each coefficient modulo $t = 24$. Since $-2 = 22 \mod 24$ we get

$$2x^{14} \cdot x^4 = 22x^2 \pmod{x^{16}+1, t}.$$

Notice that if we use the representation of $\mathbb{Z}_t$ that includes negative numbers, then $-2$ equals itself modulo $t$ and the result is still $-2x^2$, as it is said in the last parenthesis of your question.