A-10.6 Isomorphism between Polynomials and Vectors over Integers

Now, let’s define a mapping $\sigma$ from the $(n-1)$-degree polynomial ring to the $n$-dimensional vector space, such that an input polynomial’s list of $y$ values evaluated at $n$ distinct $x$ coordinates (e.g., $x_0,x_1,\cdots ,x_{n-1}$) form the mapping’s output vector. Technically, $\sigma$ is defined as:

$\sigma :f(x)\in \mathbb{Z}[X]∕(X^n+1)\to (f(x_0),f(x_1),f(x_2),\cdots ,f(x_{n-1}))\in {\mathbb{Z}}^n$

Now, we will explain why the mapping $\sigma$ is isomorphic, which means that $\sigma$ is a bijective one-to-one mapping from $\mathbb{Z}[X]∕(X^n+1)$ to ${\mathbb{Z}}^n$ and the algebraic operations $\text{(+,⋅)}$ of the mapped elements preserve correctness with homomorphism.

Bijective: In the $(n-1)$-degree polynomial ring, a list of $y$ values evaluated at some statically chosen $n$ distinct $x$ coordinates defines a unique polynomial, because algebraically there exists only one $(n-1)$-degree (or a lesser degree) polynomial that passes each given set of $n$ distinct $(x,y)$ coordinates. We proved this in Lagrange Polynomial Interpolation (Theorem A-15 in §A-15).

Homomorphic: The homomorphism of the mapping $\sigma$ on the $\text{(+,⋅)}$ operations means that the following two relationships hold:

$\sigma (f_a(X)+f_b(X))=\sigma (f_a(X))+\sigma (f_b(X))$

$\sigma (f_a(X)\cdot f_b(X))=\sigma (f_a(X))\odot \sigma (f_b(X))$ # $\odot$ is Hadamard vector multiplication (Summary A-10.1)

To prove our $\sigma$ mapping’s homomorphism, let’s denote the input polynomials $f_a(X)$, $f_b(X)$, and their $\sigma$-mapped output vectors as follows:

$f_a(X)=a_0+a_{1}X+a_2{X}^2+\cdots +a_{n-1}{X}^{n-1}$

$\sigma (f_a(X))=\left(f_a(x_0),f_a(x_1),f_a(x_2),\cdots ,f_a(x_{n-1})\right)=\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i{(x_0)}^i,\sum _{i=0}^{n-1}{a}_i{(x_1)}^i,\sum _{i=0}^{n-1}{a}_i{(x_2)}^i,\cdots ,\sum _{i=0}^{n-1}{a}_i{(x_{n-1})}^i\right)$

$f_b(X)=b_0+b_{1}X+b_2{X}^2+\cdots +b_{n-1}{X}^{n-1}$

$\sigma (f_b(X))=\left(f_b(x_0),f_b(x_1),f_b(x_2),\cdots ,f_b(x_{n-1})\right)=\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{b}_i{(x_0)}^i,\sum _{i=0}^{n-1}{b}_i{(x_1)}^i,\sum _{i=0}^{n-1}{b}_i{(x_2)}^i,\cdots ,\sum _{i=0}^{n-1}{b}_i{(x_{n-1})}^i\right)$

Given the above setup, we can see that $\sigma$ preserves homomorphism on the $\text{(+)}$ operation as follows:

$𝛔(f_a(X)+f_b(X))=𝛔((a_0+b_0)+(a_1+b_1)X+(a_2+b_2)X^2+\cdots +(a_{n-1}+b_{n-1})X^{n-1})$

$=\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(a_i+b_i){(x_0)}^i,\sum _{i=0}^{n-1}(a_i+b_i){(x_1)}^i,\sum _{i=0}^{n-1}(a_i+b_i){(x_2)}^i,\cdots ,\sum _{i=0}^{n-1}(a_i+b_i){(x_{n-1})}^i\right)$

$=\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i{(x_0)}^i,\sum _{i=0}^{n-1}{a}_i{(x_1)}^i,\sum _{i=0}^{n-1}{a}_i{(x_2)}^i,\cdots ,\sum _{i=0}^{n-1}{a}_i{(x_{n-1})}^i\right)$

$+\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{b}_i{(x_0)}^i,\sum _{i=0}^{n-1}{b}_i{(x_1)}^i,\sum _{i=0}^{n-1}{b}_i{(x_2)}^i,\cdots ,\sum _{i=0}^{n-1}{b}_i{(x_{n-1})}^i\right)$

$=𝛔(f_a(X))+𝛔(f_b(X))$

Also, we can see that $\sigma$ preservers homomorphism on the $\text{(⋅)}$ operation as follows:

$𝛔(f_a(X)\cdot f_b(X))=𝛔(\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i{X}^i\right)\cdot \left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{b}_i{X}^i\right))$

$=(\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i{x}_0^i\right)\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{b}_i{x}_0^i\right),\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i{x}_1^i\right)\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{b}_i{x}_1^i\right),\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i{x}_2^i\right)\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{b}_i{x}_2^i\right),$

$\cdots ,\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i{x}_{n-1}^i\right)\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{b}_i{x}_{n-1}^i\right))$

$=(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i{(x_0)}^i,\sum _{i=0}^{n-1}{a}_i{(x_1)}^i,\cdots ,\sum _{i=0}^{n-1}{a}_i{(x_{n-1})}^i)$

$\odot (\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{b}_i{(x_0)}^i,\sum _{i=0}^{n-1}{b}_i{(x_1)}^i,\cdots ,\sum _{i=0}^{n-1}{b}_i{(x_{n-1})}^i)$

$=𝛔(f_a(X))\odot 𝛔(f_b(X))$

In summary, $\sigma$ preserves the following homomorphism:

$\sigma (f_a(X)+f_b(X))=\sigma (f_a(X))+\sigma (f_b(X))$

$\sigma (f_a(X)\cdot f_b(X))=\sigma (f_a(X))\odot \sigma (f_b(X))$

However, for $\sigma (f_a(X)\cdot f_b(X))=\sigma (f_a(X))\odot \sigma (f_b(X))$, we need further reasoning to justify that this relation holds in polynomial rings, which is explained below.

Polynomial Ring Reduction: Suppose that we did not have the polynomial ring setup $X^n+1$. Then, if we multiply $f_a(X)$ and $f_b(X)$, then $f_a(X)\cdot f_b(X)$ may become a new polynomial whose degree is higher than $n-1$. This higher-degree polynomial would still decode into the expected correct vector. Suppose the following:

$\sigma (f_a(X))=(f_a(x_0),f_a(x_1),\cdots ,f_a(x_{n-1}))=(v_0,v_1,\cdots ,v_{n-1})$

$\sigma (f_b(X))=(f_b(x_0),f_b(x_1),\cdots ,f_b(x_{n-1}))=(u_0,u_1,\cdots ,u_{n-1})$

Then, the following is true:

$\sigma (f_a(X)\cdot f_b(X))=(f_a(x_0)\cdot f_b(x_0),f_a(x_1)\cdot f_b(x_1),\cdots ,f_a(x_{n-1})\cdot f_b(x_{n-1}))=(v_0{u}_0,v_1{u}_1,\cdots ,v_{n-1}{u}_{n-1})$

$=(v_0,v_1,\cdots ,v_{n-1})\odot (u_0,u_1,\cdots ,u_{n-1})$

As shown above, even if $f_a(X)\cdot f_b(X)$ results in a polynomial with a degree higher than $n-1$, it can be decoded into the expected correct vector. However, the $\sigma$ mapping loses the property of isomorphism between a polynomial and a vector, because if a polynomial’s degree is higher than $n-1$, then there can be more than 1 polynomial that passes through the given $n$ distinct $X$ coordinates: $\{x_0,x_1,\cdots ,x_{n-1}\}$. This is a problem, because if the $\sigma$ mapping supports only polynomial-to-vector mappings and not vector-to-polynomial mappings, then we cannot convert vectors into polynomials in the first place and do isomorphic computations. Another minor issue is that if the polynomial degree term is higher than $n-1$, then the computation overhead of decoding (i.e., polynomial evaluation) becomes larger than before.

To resolve these two minor issues, we let the $n$ distinct $X$ coordinates of evaluation to be the solutions of the polynomial ring modulo $X^n+1$ (where $n$ is some power of 2), and reduce $f_a(X)\cdot f_b(X)$ to a new polynomial modulo $X^n+1$ whose degree is at most $n-1$. Let $f_{\mathit{𝑎𝑏}}(X)=f_a(X)\cdot f_b(X)$, and $f_{\mathit{𝑎𝑏}}^{\prime }(X)$ is the reduced polynomial such that $f_{\mathit{𝑎𝑏}}(X)=Q(X)\cdot (X^n+1)+f_{\mathit{𝑎𝑏}}^{\prime }(X)$ for some quotient polynomial $Q(X)$. Then, as illustrated in Summary A-5.1.2 (§A-5.1.2), $f_{\mathit{𝑎𝑏}}(X)$ and $f_{\mathit{𝑎𝑏}}^{\prime }(X)$ evaluate to the same value if they are evaluated at the roots of $X^n+1$ (by zeroing out the $Q(X)$ term). Therefore, if we let the $n$ distinct evaluating points $\{x_0,x_1,\cdots ,x_{n-1}\}$to be the roots of $X^n+1$, then we can ensure that the decoded vector of $f_{\mathit{𝑎𝑏}}^{\prime }(X)$ is identical to that of $f_{\mathit{𝑎𝑏}}(X)$ which we expect. Therefore, we can replace the higher-degree polynomial $f_{\mathit{𝑎𝑏}}(X)$ with the reduced polynomial $f_{\mathit{𝑎𝑏}}^{\prime }(X)$ and continue with any further polynomial additions or multiplications by using $f_{\mathit{𝑎𝑏}}^{\prime }(X)$. Also, by applying polynomial ring reduction, we can enhance the computational efficiency of polynomial addition/multiplication as well as preserve the isomorphism of the $\sigma$ mapping, and therefore we can freely convert between vectors & polynomials and do additions/multiplications.

For applying this polynomial ring reduction, the polynomial modulus can be any polynomial as far as it has at least $n$ distinct roots. In practice, we often choose $X^n+1$ as the polynomial ring modulus, which is the $(\mu =2n)$-th cyclotomic polynomial (§A-8.1). The reason why we let the polynomial ring modulus be a cyclotomic polynomial (especially the $(\mu =2n)$-th cyclotomic polynomial, $X^n+1$) is because its $n$ distinct roots are well-defined (i.e., primitive $(\mu =2n)$-th roots of unity) and thus can be quickly computed even in the case $n$ is large.

Polynomial Coefficient Modulo Reduction: In addition, we often reduce the polynomial coefficients based on some modulus $t$, to keep the size of the coefficients lower than a certain limit for the purpose of computational efficiency. Suppose two polynomials $f_c(X)$ and $f_d(X)$ have congruent coefficients modulo $t$ as follows:

$f_c(X)=w_0+w_1\cdot x_i+w_2\cdot x_i^2+\cdots +w_{n-1}\cdot x_i^{n-1}$

$f_d(X)=w_0^{\prime }+w_1^{\prime }\cdot x_i+w_2^{\prime }\cdot x_i^2+\cdots +w_{n-1}^{\prime }\cdot x_i^{n-1}$

$w_i\equiv w_i^{\prime }modt$

Then, their evaluated value $f_c(x_i)$ and $f_d(x_i)$ for any $x_i$ is guaranteed to be congruent modulo $t$, as shown below:

$f_c(x_i)=w_0+w_1\cdot x_i+w_2\cdot x_i^2+\cdots +w_{n-1}\cdot x_i^{n-1}$

$\equiv (w_0+w_1\cdot x_i+w_2\cdot x_i^2+\cdots +w_{n-1}\cdot x_i^{n-1})modt$

$\equiv (w_{0}modt)+(w_{1}modt)\cdot x_i+(w_{2}modt)\cdot x_i^2+\cdots +(w_{n-1}modt)\cdot x_i^{n-1})$

$\equiv w_0^{\prime }+w_1^{\prime }\cdot x_i+w_2^{\prime }\cdot x_i^2+\cdots +w_{n-1}^{\prime }\cdot x_i^{n-1}$

$=f_d(x_i)$

Summary: Since $\sigma$ is bijective and homomorphic, $\sigma$ is an isomorphic mapping between the $(n-1)$-degree polynomial ring ${\mathbb{Z}}_t[X]∕X^n+1$ and the $n$-dimensional vector space ${\mathbb{Z}}_t^n$.

A-10.6.1 Finding Appropriate Modulus $t$

To isomorphically evaluate a polynomial in ${\mathbb{Z}}_t[X]∕X^n+1$ into an $n$-dimensional vector, we need to evaluate the polynomial at $n$ distinct roots of $X^n+1modt$. However, $X^n+1modt$ does not have $n$ distinct roots for all combinations of (degree, modulus) $=(n,t)$. For example, if $n=2$ and $t=3$, then $X^2+1\not\equiv 0mod3$ for any possible values of $X=\{0,1,2\}$. Therefore, our goal is to find a satisfactory $t$ given a fixed $n$ such that $n$ distinct roots of $X^n+1(\mathit{𝑚𝑜𝑑}t)$ exist, in order to use the isomorphic $\sigma$ mapping.

We start with two constraints: (1) we choose $t$ only such that $t$ is a prime number $p$; (2) $\mathit{𝑡–}1$ is some multiple of $2n$ (i.e., $(\mathit{𝑡–}1)=k\cdot 2n$ for some integer $k$).

We learned from Fermat’s Little Theorem in Theorem A-4.2.4 (§A-4.2) the following: $a^{t-1}\equiv 1modt$ if and only if $a$ and $t$ are co-prime. This means that if $t$ is a prime, then $a^{t-1}\equiv 1modt$ for all $a\in {\mathbb{Z}}_t^{\times }$ (i.e., ${\mathbb{Z}}_t$ without $\{0\}$). Suppose $g$ is the generator of ${\mathbb{Z}}_t^{\times }$ whose powered values generate all elements of ${\mathbb{Z}}_t^{\times }$. Then, ${\mathsf{\text{𝖮𝗋𝖽}}}_{{\mathbb{Z}}_t}(g)=t-1$, and $g^{t-1}\equiv 1modt$. Since $t-1=k\cdot 2n$ for some $k$, $g^{k\cdot 2n}\equiv {(g^k)}^{2n}\equiv 1modt$. Then, ${\mathsf{\text{𝖮𝗋𝖽}}}_{{\mathbb{Z}}_t}(g^k)\le 2n$. However, since ${\mathsf{\text{𝖮𝗋𝖽}}}_{{\mathbb{Z}}_t}(g)=t-1$, for all $a$ such that $a<\mathit{𝑡–}1=k\cdot 2n$, $g^a\not\equiv 1modt$. In other words, for all $b$ such that $b<2n$, ${(g^k)}^b\not\equiv 1modt$. Thus, ${\mathsf{\text{𝖮𝗋𝖽}}}_{{\mathbb{Z}}_t}(g^k)=2n$.

Let $c=g^k$. Since ${\mathsf{\text{𝖮𝗋𝖽}}}_{{\mathbb{Z}}_t}(c)=2n$, $c^{2n}\equiv 1modt$. In other words, ${(c^n)}^2\equiv 1modt$. Now, $c^n$ can be only 1 or -1. The reason is that in the relation $X^2\equiv 1modt$, $X$ can be mathematically only $1$ or $-1\equiv \mathit{𝑡–}1modt$. If we substitute $X=c^n$, then $c^n$ can be only $1$ or $-1\equiv t-1modt$. But ${\mathsf{\text{𝖮𝗋𝖽}}}_{{\mathbb{Z}}_t}(c)=2n$, thus $c^n$ cannot be 1 (because $1^1=1$ and 1 is smaller than the order of $c$: $2n>1$). Thus, $c^n$ can be only $-1\equiv \mathit{𝑡–}1modt$. If $c^n=-1\equiv t-1modt$, then $c$ is the root of $X^n+1modt$, because $X^n+1=c^n+1\equiv (t-1)+1\equiv 0modt$.

In conclusion, given a cyclotomic polynomial $X^n+1$, if we choose a prime $t$ such that $\mathit{𝑡–}1=k\cdot 2n$ for some integer $k$, then one root of $X^n+1modt$ is: $X=c=g^k$.

Once we have found one root of $X^n+1$, then we can derive all $n$ distinct roots of $X^n+1$. Suppose $\omega$ is one root of $X^n+1modt$. Then, we derive the following:

${\omega }^n+1\equiv 0modt$

${\omega }^n\equiv t-1modt$

${\omega }^{2n}\equiv (t-1)\cdot (t-1)\equiv t^2–2t+1\equiv 1modt$

While ${\omega }^{2n}\equiv 1modt$, ${\omega }^n\not\equiv 1modt$, because if so, $X^n+1={\omega }^n+1=1+1=2\ne 0$, which contradicts the fact that $\omega$ is a root of $X^n+1$. Therefore, ${\mathsf{\text{𝖮𝗋𝖽}}}_{{\mathbb{Z}}_t}(c)=2n$.

Now, we derive the remaining $n-1$ distinct roots of $X^n+1modt$ as follows:

${({\omega }^3)}^n+1\equiv ({\omega }^{2n})\cdot {\omega }^n+1\equiv {\omega }^n+1\equiv t-1+1\equiv 0modt$

${({\omega }^5)}^n+1\equiv ({\omega }^{4n})\cdot {\omega }^n+1\equiv {\omega }^n+1\equiv t-1+1\equiv 0modt$

$⋮$

${({\omega }^{2n-1})}^n+1\equiv ({\omega }^{2n-2})\cdot {\omega }^n+1\equiv {\omega }^n+1\equiv t-1+1\equiv 0modt$

Note that $\omega ,{\omega }^3,{\omega }^5,\cdots ,{\omega }^{2n-1}$ are all distinct values in ${\mathbb{Z}}_t^{\times }$, because ${\mathsf{\text{𝖮𝗋𝖽}}}_{{\mathbb{Z}}_t}(c)=2n$. Thus, ${\{{\omega }^{2i+1}\}}_{i=0}^{n-1}$ are $n$ distinct roots of $X^n+1$. At the same time, since these are the roots of the cyclotomic polynomial $X^n+1$, these are $n$ distinct primitive $(\mu =2n)$-th roots of unity.

We summarize our findings as follows: