2
$\begingroup$

Imagine that I have two vectors of polynomials $\mathbf{v}, \mathbf{u}$ where $\mathbf{v} = (f_1, f_2, \dots, f_m)$ and $\mathbf{u} = (g_1, g_2, \dots, g_m)$ with $f_i,g_i \in\mathbb{Z}_q[x] / \langle x^n+1\rangle$ for $i \in [m]$. Recall that, when $n$ is a power of $2$, $\mathbb{Z}_q[x] / \langle x^n+1\rangle$ is the ring of polynomials with degree at most $n-1$ with coefficients from $\mathbb{Z}_q = \{0, 1, \dots, q-1\}$ for a prime $q$. Hence, each $f \in \mathbb{Z}_q[x] / \langle x^n+1\rangle$ has the form $$f = a_0 + a_1x + \dots + a_{n-1}x^{n-1}.$$

My objective is to perform the operation (I represent vectors as column vectors) $$\mathbf{u}^T \cdot \mathbf{v}= h\in \mathbb{Z}_q[x] / \langle x^n+1\rangle$$ but in matrix form, i.e., I would like to somehow represent these vectors as matrices with coefficients in $\mathbb{Z}_q$ such that their product gives a vector $\mathbf{h} = (h_0, h_1, \dots, h_{n-1}) \in \mathbb{Z}_q^n$ such that $$h = h_0 + h_1x + \dots + h_{n-1}x^{n-1}.$$ This is the natural embedding of vectors in polynomials and vice-versa.

I am not sure how to do it. Any help will be appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ Is this a question or a simple post ? I had to edit it to make it look like a question. $\endgroup$
    – Spectre
    Commented Aug 26, 2020 at 8:55

1 Answer 1

3
$\begingroup$

If $P$ denotes the permutation matrix $$ P = \pmatrix{&&&-1\\ 1\\ &\ddots \\ &&1}, $$ then the map to the circulant matrices defined by $f \mapsto f(P)$ is an isomorphism of rings. With that established, $u^Tv$ can be calculated with the block-matrix product $$ (u^Tv)(P) = \pmatrix{g_1(P) & \cdots & g_m(P)} \pmatrix{f_1(P) \\ \vdots \\ f_m(P)}. $$

$\endgroup$
2
  • $\begingroup$ I am choosing $x^n+1$ to be the quotient, so every element above the diagonal in your $f(P)$ should have a minus sign. For my objective, I think that I just have to consider the first column of every product $g_i(P)f_i(P)$, because the rest are just permutations of the first column. Am I right? $\endgroup$
    – Bean Guy
    Commented Aug 26, 2020 at 9:54
  • 1
    $\begingroup$ Yes, I was indeed missing the minus sign. I don't know what you mean by "just having to consider the first column of every product." You need at least one of the two matrices in full in order to compute the first column of the product. It is certainly possible to replace the block matrix corresponding to $v$ with a column-vector, if that's what you mean. And of course, once you have computed the product in the way I prescribe, the coefficients can be extracted from the first column. $\endgroup$ Commented Aug 26, 2020 at 10:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .