# What is $\mathbb{Z_p}$ when $p$ is polynomial?

--- 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.

• 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). – Eike Schulte Oct 14 '15 at 19:19
• @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... – Hilder Vítor Lima Pereira Oct 14 '15 at 20:02
• 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$. – 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.