SEAL Homomorphic multiplication In SEAL homomorphic encryption library, there is an internal procedure to decompose a polynomial with large coefficients into a vector of polynomials with smaller coefficients. The procedure is described in pages 3-4 here. I wonder if someone can paraphrase the procedure and provide a simple example to show how polynomial multiplication can be done via that procedure and why it is better than school-book polynomial multiplication followed by modular reduction.

Let $n = 4$, $q = 199$, $w = 16$. This means that $\ell_{w,q}=2$, $\mathbb{Z}_q = \{-99,...,99\}$, and $\mathbb{Z}_w = \{-8,...,7\}$.

Let $a = 70X^2 + 56X+45$ and $b = 61X+31$.

Please show $Dec_{w,q}(a)$ and $Pow_{w,q}(b)$ and how the dot product is equivalent to polynomial multiplication as follows: $\langle Dec_{w,q}(a),Pow_{w,q}(b) \rangle = a.b \pmod q$.
In this answer, I am reducing using that centered representation of $\mathbb{Z}_q$ and $\mathbb{Z}_w$. Also, I am writing $\ell$ instead of $l_{w,q}$ to simplify the notation.

Concrete examples:


$Dec_{w,q}(a) = (6x^2 - 8x - 3, 4x^2 + 4x + 3)$
$Pow_{w,q} = (61x + 31, 61\cdot16x + 31\cdot16) = (61x + 31, -19 x + 98) \pmod q $


Therefore, we have the following dot product:

$$\begin{align}
Dec_{w,q}(a)\cdot Pow_{w,q}(b) &amp;= (6x^2 - 8x - 3) \cdot (61x + 31)+( 4x^2 + 4x + 3) \cdot  (-19 x + 98) \\
                 &amp;= (366 x^3-302 x^2-431 x-93) + (-76x^3+316 x^2+335 x+294)\\
                 &amp;= 290 x^3+14 x^2-96 x+201 \\
                 &amp;= 91x^3 + 14x^2  -96x + 2
\end{align}$$

And the usual product reduced modulo $q$ is:

$a \cdot b = 4270 x^3+5586 x^2+ 4481x+1395 = 91x^3 + 14x^2 + -96x + 2$

Explanation:

In order to have a simple understanding, think of the integers (or, polynomials with degree equal to zero): in this case, it is easy to see that given an integer $a$, we can write $a$ in base $w$ obtaining digits $a_\ell, ..., a_1, a_0$ such that 

$$a = \sum_{i=0}^\ell a_i \cdot w^i$$

In particular, if $w = 2$, then this is the binary representation.

The key point now is to understand why it is still valid if $a$ is any polynomial. In fact, it is valid because we just write each coefficient in base $w$, obtaining $\ell$ digits for each coefficient and then we define $\ell$ polynomials, with each polynomial $a_i$ having the $i$-th digits of each coefficient...

For instance, let $p(x) = 3x^3 + 2x + 1$, $q = 199$ and $w = 2$, then, write each coefficient in base $w$, obtaining $3 = (1,1)_w$, $2 = (0,1)_w$, and $1 = (1, 0)_w$, thus, we got 
$$Dec_{w,q}(p) = (\underbrace{1x^3 + 0x + 1}_{\text{First digits}}, \underbrace{1x^3 + 1x + 0}_{\text{Second digits}})$$

So, once we have accepted that the summation above holds for any polynomial $a$, i.e., we can decompose any polynomial writing its coefficients in base $w$, then, understanding why the dot product is equal to the usual product is straightforward.

The function $Pow_{w,q}(b)$ just put the exponents of the decomposition of  the summation above in a vector with the polynomial $b$: $Pow_{w,q}(b) = (b\cdot w^0, b\cdot w^1, ..., b\cdot w^\ell)$.

Therefore, we have

$$
\begin{align}
Dec_{w,q}(a) \cdot Pow_{w,q}(b) &amp;= (a_0, ..., a_\ell) (b\cdot w^0, ..., b\cdot w^\ell) &amp; \\
 &amp;= \sum_{i=0}^\ell a_i b w^i &amp; (\text{By defn. of dot product}) \\
 &amp;= b \sum_{i=0}^\ell a_i  w^i &amp; (\text{Since } b \text{ doesn't depend on } i)\\
&amp;= b a  &amp; (\text{With the above equality})
\end{align}
$$

About your other issue:


  why it is better than school-book polynomial multiplication followed
  by modular reduction.


I think you have miss understood SEAL's manual... Those two functions are used in the relinearization step (called KeySwitch on the original paper), and they are not used to increase the efficiency of the multiplication, they are used to guarantee the correctness of the decryption under the original private key (and also to manage the noise growth). I suggest that you read section 5 of the original YASHE paper.