# Polynomial equations with finite field arithmetic

there are given 3 equations (they are connected with cyclic codes): $$s(x)=v(x)+q(x)g(x)$$ $$g(x)h(x)=x^7+1$$ $$s(x)=v(x)h(x)\bmod(x^7+1)$$

I have following data (for $GF(8)$ with generator polynomial $p(x)=x^3+x+1$): $$g(x)=x^4+\alpha^3x^3+x^2+\alpha x+\alpha^3$$ $$q(x)=\alpha^6 x^2 + \alpha^2 x + \alpha$$ $$v(x)=\alpha^6 x^6 + \alpha^3 x^3 + \alpha^6 x^2 + x + \alpha^4$$

So I use first equation and: $$s(x)=v(x)+q(x)g(x)$$$$=(\alpha^6 x^6 + \alpha^3 x^3 + \alpha^6 x^2 + x + \alpha^4)+(\alpha^6 x^2 + \alpha^2 x + \alpha)(x^4+\alpha^3x^3+x^2+\alpha x+\alpha^3)$$ $$=(\alpha^6 x^6 + \alpha^3 x^3 + \alpha^6 x^2 + x + \alpha^4)+(\alpha^6 x^6 + \alpha^3 x^3 + \alpha^6 x^2 + \alpha^3x + \alpha^4)=\alpha x$$

And it's all right until now - result is correct. Now let's see second equation:

$$h(x)=\frac{x^7+1}{g(x)}=x^3+\alpha^3x^2+\alpha^2x+\alpha^4$$

And using third equation:

$$s(x)=v(x)h(x)\bmod(x^7+1)$$

$$s(x)=(\alpha^6 x^6 + \alpha^3 x^3 + \alpha^6 x^2 + x + \alpha^4)(x^3+\alpha^3x^2+\alpha^2x+\alpha^4)\bmod(x^7+1)$$

$$s(x)=\alpha^6 x^9 + \alpha^2 x^8 + \alpha x^7 + \alpha x^4 + \alpha^4 x^3 + \alpha^4 x^2 + \alpha^3 x + \alpha \bmod (x^7+1)$$

$$\frac{\alpha^6 x^9 + \alpha^2 x^8 + \alpha x^7 + \alpha x^4 + \alpha^4 x^3 + \alpha^4 x^2 + \alpha^3 x + \alpha}{x^7+1}$$$$=(\alpha^6 x^2 + \alpha^2 x + \alpha) + (\alpha x^4 + \alpha^4 x^3 + \alpha^3 x^2 + \alpha^5 x)$$

so

$$s(x)=\alpha x^4 + \alpha^4 x^3 + \alpha^3 x^2 + \alpha^5 x$$

Problem is that the result of $s(x)$ calculated with first and third equations is not the same. It should be the same for $s(x)$ of degree less than degree of $g(x)$.

-
+1 for typing all that out! – Chris Taylor May 25 '11 at 11:32

Your third equation should be $\rm\ s(x)\ h(x)\equiv v(x)\ h(x)\ \ (mod\ x^7 + 1)\:,\:$ which agrees with the calculations. It arises by multiplying the first equation by $\rm\:h(x)\:,\:$ then using the second equation.