2

I have 2 polynomials $P(x)$ and $Q(x)$ over a finite ring $R(x)=x^p +1$. Let $M(x)=P(x) Q(x)$ over that ring.

Example: $P(x)=x-1$, and $Q(x)=x^2+x+1$, then $M(x)=x^3-1=-2$ over that ring $R(x)=x^3+1$

My question: Given a value $\alpha$, I can compute $p=P(\alpha)$ and $q=Q(\alpha)$. How to compute $M(\alpha)$ from $p$ and $q$ without computing the polynomial multiplication $P(x)Q(x)$?

Example: with $\alpha =1$, we have $p=0, q=3$, but $M(1)$ is always equal to $-2$. Multiplying $pq$ gives a wrong answer.

Niko
  • 21
  • 1
    What do you mean by "...over a finite ring $R(x)=x^p+1$".? Do you mean over a finite ring of $p$ elements? Or a finite ring of characteristic $p$? Or something else? – Servaes Jul 29 '19 at 17:27
  • On a second reading; do you mean a finite ring in which $x^p+1=0$ for all $x$? – Servaes Jul 29 '19 at 17:31
  • yes, $p$ is a prime. For example, a polynomial $A(x)=2x^{(p+1)}+1$ is equal to a polynomial $-2x+1$ since $A(x)=2x(x^p+1)-2x+1 = -2x+1$ mod $x^p+1$ – Niko Jul 29 '19 at 17:50
  • You did not answer my question; I agree that $2x^{p+1}+1\equiv-2x+1\pmod{(x^p+1)}$ over any ring, but do you assume that $x^p+1=0$ for every element $x$ of your ring? – Servaes Jul 29 '19 at 18:25

1 Answers1

0

If you know $p=P(\alpha)$ and $q=Q(\alpha)$ then $M(\alpha)=P(\alpha)Q(\alpha)=pq$. So you can compute the product of two elements of the finite ring, in stead of the product of two polynomials over the finite ring.

In your particular example; if you find that $p=0$ and $q=3$ and so $M(\alpha)=pq=0$. But you also find that $M(x)=x^3-1=-2$ because $x^3+1=0$ for all $x$. There is nothing wrong here; if $x^3+1=0$ for all $x$ then in particular $2=1^3+1=0$ and hence also $-2=0$.

Servaes
  • 63,261
  • 7
  • 75
  • 163
  • Thank you for your answer. I was thinking about a solution, which computes $P(\alpha) Q(\alpha) mod (\alpha^p +1)$ to get $M(\alpha)$, but I am not sure whether this solution is correct. – Niko Jul 29 '19 at 18:07