1
$\begingroup$

Imagine I have these equations $$x^2 = x \cdot x \; \land \; 0 = x^2-x,$$ and I ask for a solution in $\mathbb{Z}_q = \{0,1,\dots,q-1\}$ where $q$ is a prime number. It is easy to see that the only solutions to these equations are $0$ and $1$.

However, if we ask for solutions in the polynomial ring $\mathcal{R}_q = \mathbb{Z}_q[x]/\langle x^n+1 \rangle$ where $n=2^k$ with $k \in \mathbb{N}$ (i.e., $\mathcal{R}_q$ is the ring of polynomials with coefficients in $\mathbb{Z}_q$ of degree at most $n-1$), there are different from $0$ or $1$ as we are not working in a field anymore.

I am wondering if there are some set of equations that are only satisfied by $0$ and $1$ in $\mathcal{R}_q$.

$\endgroup$

1 Answer 1

2
$\begingroup$

There are not, in general. The problem is that your ring can in general be written as a product of other rings (whenever $x^n + 1$ has a nontrivial factorization $\bmod q$), and the solutions to a system of polynomial equations in a product $R \times S$ have the following property:

$(r, s)$ is a solution iff $r$ is a solution to the system when projected down to $R$ and $s$ is a solution to the system when projected down to $S$.

It follows that if $(0, 0)$ and $(1, 1)$ are both solutions then $0$ and $1$ are both solutions to the system projected down to both $R$ and $S$, which means that necessarily $(0, 1)$ and $(1, 0)$ must also be solutions.

By the way, this:

i.e., $\mathcal{R}_q$ is the ring of polynomials with coefficients in $\mathbb{Z}_q$ of degree at most $n-1$

is not an accurate description of $R_q$. "Polynomials of degree at most $n-1$" only forms a vector space and multiplication can be defined in many different ways.

$\endgroup$

You must log in to answer this question.

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