A-10.6 Isomorphism between Polynomials and Vectors over Integers (and Ring)

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\; \in \; \mathbb{Z}$ coordinates (e.g., $x_0,x_1,\cdots ,x_{n-1}$) forms 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 it preserves the algebraic operations $(+,\cdot )$ (i.e., $\sigma$ is a homomorphism for addition and multiplication).

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 through 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 $(+,\cdot )$ 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 }}{a}_i{(x_0)}^i,\underset{i=0}{\overset{n-1}{\sum }}{a}_i{(x_1)}^i,\underset{i=0}{\overset{n-1}{\sum }}{a}_i{(x_2)}^i,\cdots ,\underset{i=0}{\overset{n-1}{\sum }}{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 }}{b}_i{(x_0)}^i,\underset{i=0}{\overset{n-1}{\sum }}{b}_i{(x_1)}^i,\underset{i=0}{\overset{n-1}{\sum }}{b}_i{(x_2)}^i,\cdots ,\underset{i=0}{\overset{n-1}{\sum }}{b}_i{(x_{n-1})}^i\right)$

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

$\mathbf{\text{𝛔}}\mathbf{\text{(}}{f}_a(X)\; +f_b(X)\mathbf{\text{)}}=𝛔((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 }}(a_i+b_i){(x_0)}^i,\underset{i=0}{\overset{n-1}{\sum }}(a_i+b_i){(x_1)}^i,\underset{i=0}{\overset{n-1}{\sum }}(a_i+b_i){(x_2)}^i,\cdots ,\underset{i=0}{\overset{n-1}{\sum }}(a_i+b_i){(x_{n-1})}^i\right)$

$=\left(\underset{i=0}{\overset{n-1}{\sum }}{a}_i{(x_0)}^i,\underset{i=0}{\overset{n-1}{\sum }}{a}_i{(x_1)}^i,\underset{i=0}{\overset{n-1}{\sum }}{a}_i{(x_2)}^i,\cdots ,\underset{i=0}{\overset{n-1}{\sum }}{a}_i{(x_{n-1})}^i\right)$

$+\left(\underset{i=0}{\overset{n-1}{\sum }}{b}_i{(x_0)}^i,\underset{i=0}{\overset{n-1}{\sum }}{b}_i{(x_1)}^i,\underset{i=0}{\overset{n-1}{\sum }}{b}_i{(x_2)}^i,\cdots ,\underset{i=0}{\overset{n-1}{\sum }}{b}_i{(x_{n-1})}^i\right)$

$=\mathbf{\text{𝛔(}}{f}_a(X)\mathbf{\text{)}}+\mathbf{\text{𝛔(}}{f}_b(X)\mathbf{\text{)}}$

Also, we can see that $\sigma$ preserves homomorphism on the $(\cdot )$ operation as follows:

$\mathbf{\text{𝛔(}}{f}_a(X)\; \cdot f_b(X)\mathbf{\text{)}}=𝛔(\left(\underset{i=0}{\overset{n-1}{\sum }}{a}_i{X}^i\right)\cdot \left(\underset{i=0}{\overset{n-1}{\sum }}{b}_i{X}^i\right))$

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

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

$=(\underset{i=0}{\overset{n-1}{\sum }}{a}_i{(x_0)}^i,\underset{i=0}{\overset{n-1}{\sum }}{a}_i{(x_1)}^i,\cdots ,\underset{i=0}{\overset{n-1}{\sum }}{a}_i{(x_{n-1})}^i)$

$\odot (\underset{i=0}{\overset{n-1}{\sum }}{b}_i{(x_0)}^i,\underset{i=0}{\overset{n-1}{\sum }}{b}_i{(x_1)}^i,\cdots ,\underset{i=0}{\overset{n-1}{\sum }}{b}_i{(x_{n-1})}^i)$

$=\mathbf{\text{𝛔(}}{f}_a(X)\mathbf{\text{)}}\odot \mathbf{\text{𝛔(}}{f}_b(X)\mathbf{\text{)}}$

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 computational 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 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_{ab}(X)\; =f_a(X)\; \cdot f_b(X)$, and $f_{ab}^{\prime }(X)$ be the reduced polynomial such that $f_{ab}(X)\; =\; Q(X)\; \cdot (X^n+\; 1)\; +f_{ab}^{\prime }(X)$ for some quotient polynomial $Q(X)$. Then, as illustrated in Summary A-5.1.2 (§A-5.1.2), $f_{ab}(X)$ and $f_{ab}^{\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}\}$be the roots of $X^n+\; 1$, then we can ensure that the decoded vector of $f_{ab}^{\prime }(X)$ is identical to that of $f_{ab}(X)$, which we expect. Therefore, we can replace the higher-degree polynomial $f_{ab}(X)$ with the reduced polynomial $f_{ab}^{\prime }(X)$ and continue with any further polynomial additions or multiplications using $f_{ab}^{\prime }(X)$. Also, by applying polynomial ring reduction, we can enhance the computational efficiency of polynomial addition and multiplication, as well as preserve the isomorphism of the $\sigma$ mapping. Therefore, we can freely convert between vectors & polynomials and perform additions and multiplications.

For applying this polynomial ring reduction, the polynomial modulus can be any polynomial as long 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 we let the polynomial ring modulus be a cyclotomic polynomial (especially the $(\mu \; =\; 2n)$-th cyclotomic polynomial, $X^n+\; 1$) is that its $n$ distinct roots are well-defined (i.e., primitive $(\mu \; =\; 2n)$-th roots of unity) and thus can be quickly identified even when $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(modt)$ exist in order to use the isomorphic $\sigma$ mapping.

We start with two constraints: (1) choose $t$ to be a prime number; (2) ensure $t\; -1$ is a multiple of $2n$.

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 , $g^a\not\equiv 1modt$. In other words, for all $b$ such that , ${(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 t\; -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 t\; -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 $t\; -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 0modt$
$▹$for any odd $k\; =\; 2j\; +\; 1$, ${({\omega }^{2j+1})}^n={({\omega }^{2n})}^j\cdot {\omega }^n=1^j\cdot (-1)\; =\; -1$, so ${({\omega }^k)}^n+\; 1\; =\; 0$

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: