--- Short --

What is the ring $\frac{\mathbb{Z}_p[x]}{x^n + 1}$ if we allow $p$ to be a polynomial?

-- Contextualized question --

In the paper Efficient Integer Encoding for Homomorphic Encryption via Ring Isomorphisms, a cryptographic scheme that uses a ring $R_p = \frac{\mathbb{Z}_p[x]}{x^n + 1}$, where $p$ is a integer, is modified to create a encoding method...

So, the authors choose $p = x - a$, for some $a \in \mathbb{Z}$ and say that they will work with the quotient ring $R_{x -a} = \frac{\mathbb{Z}[x]}{(x^n + 1, x - a)}$

First of all, I am not sure that $R_{x -a} = \frac{\mathbb{Z}[x]}{(x^n + 1, x - a)}$ is the samething of $R_{x -a} = \frac{\mathbb{Z}_{x - a}[x]}{x^n + 1}$, but I think it is the case.

Second, I don't know what the authors mean there. It seems like "integers modulo the polynomial $x - a$", but I don't know this structure.

Then, please, if you know what the authors are saying, explain it to me.

Thank you very much.

  • 1
    $\begingroup$ As far as I can see it, they never use $\mathbb{Z}_p$ where $p$ is a polynomial. You have $R = \mathbb{Z}[x]/\langle x^n+1\rangle$, $R_p = \mathbb{Z}[x]/\langle x^n + 1, p\rangle$ for $p \in \mathbb{Z}$ (which you can also write as $\mathbb{Z}_p[x]/\langle x^n + 1\rangle$) and finally $R_p = \mathbb{Z}[x]/\langle x^n + 1, p\rangle$ for a polynomial $p$ (which you can’t write in the alternative form, precisely because $p$ is a polynomial). $\endgroup$ – Eike Schulte Oct 14 '15 at 19:19
  • $\begingroup$ @EikeSchulte, so, please, could you tell me what is $\mathbb{Z}[x]/(x^n + 1, p)$ ? I do not understand this notation with two values on the module... $\endgroup$ – Hilder Vítor Lima Pereira Oct 14 '15 at 20:02
  • 2
    $\begingroup$ You take the ideal $I$ of the polynomial ring $\mathbb{Z}[x]$ generated by the two polynomials $x^n + 1$ and $p$ and then consider the usual quotient ring $\mathbb{Z}[x]/I$. $\endgroup$ – Eike Schulte Oct 14 '15 at 21:01

It seems like "integers modulo the polynomial $x - a$", but I don't know this structure.

"Integers modulo a polynomial" doesn't make sense: the ideal of a quotient ring must be an ideal of the ring you are working in.

The ring $\frac{\mathbb{Z}[x]}{(x^n + 1, x - a)}$, on the other hand, does not suffer that problem since the ideal generated is in $\Bbb Z[x]$. By the third isomorphism theorem this ring is isomorphic to

$$\frac{\frac{\Bbb Z[x]}{(x-a)}}{\frac{(x^n+1,x-a)}{(x-a)}}\cong \frac{\Bbb Z}{(a^n+1)}=\Bbb Z_{a^n+1}$$

The ring $\frac{\mathbb{Z}[x]}{(x^n + 1, p)}$ is much more familiar to me. By the third isomorphism theorem it is isomorphic to $$\frac{\frac{\Bbb Z[x]}{(p)}}{\frac{(x^n+1,p)}{(p)}}\cong \frac{\Bbb Z_p[x]}{(x^n+1)}$$

I thought I had heard them in the context of "skew-cyclic" or "pseudo-cyclic" or "quasi-cyclic" linear codes in algebraic coding theory, but I can't seem to track down which adjective was used or if it was widespread.

The ordinary cyclic codes over finite fields are, of course, just ideals of the ring $\frac{F[x]}{(x^n-1)}$ where $F$ is a finite field.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.