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

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?

• Do you know how to do polynomial division? – DRF Nov 28 '18 at 14:36

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.