Compute $a(x)b(x)+c(x)$ in $\mathrm{GF}(2^4)$ where the irreducible generator polynomial $x^4+x+1$.

Let the coefficients of $$a(x) = x^3+x^2+1,$$ $$b(x) = x^2+x+1,$$ $$c(x) = x^3+x^2+x+1$$ be in $\mathrm{GF}(2)$. Compute $a(x)b(x)+c(x)$ in $\mathrm{GF}(2^4)$ where the irreducible generator polynomial $x^4+x+1$.

This is the exact question in a criptography lesson midterm. I have calculated the $a(x)b(x)+c(x) = x^5 + 2x^4 + 3x^3 + 3x^2 + 2x + 1$. As I know in a $\mathrm{GF}(2^4)$, coefficients can't be greater than 15. So it is ok for a intermediate result. Now what to do with $x^4+x+1$? Can you help me?

• I am sorry but i could not understand what you are asking for.. could you please a bit more preciese..
– user87543
Nov 30, 2013 at 16:43
• You have to take the remainder module $x^4+x+1$. Indeed, you generated $GF(2^4)$ by taking it to be $GF(2)[x] / (x^4+x+1)$. Nov 30, 2013 at 16:57
• The only way this makes sense is what Pablo suggests. Strictly speaking you are no longer dealing with polynomials, but their cosets. A remotely possible alternative would be that you should treat $a(x),b(x),c(x)$ as elements of the polynomial ring $GF(16)[x]$. But because their coefficients are in the subfield $GF(2)$ I don't see the need to talk about $GF(16)$ at all, if this were the intention. But you comment about coefficients being at most 15 worries me quite a bit. Are you sure that you know what $GF(16)$ is? Nov 30, 2013 at 17:58

I just added a self-answered question giving a useful discrete logarithm table. I rely heavily on that. Below $\gamma$ will denote the coset $x+I$ in the quotient ring $GF(2)[x]/I$, where the ideal $I=\langle x^4+x+1\rangle$. That table then tells us that \begin{aligned} a(x)+I&=x^3+x^2+1+I=\gamma^3+\gamma^2+1=\gamma^{13},\\ b(x)+I&=x^2+x+1+I=\gamma^2+\gamma+1=\gamma^{10},\\ c(x)+I&=x^3+x^2+x+1+I=\gamma^3+\gamma^2+\gamma+1=\gamma^{12}. \end{aligned} Thus $$a(x)b(x)+I=\gamma^{13}\cdot\gamma^{10}=\gamma^{23}=\gamma^{15+8}=\gamma^8=\gamma^2+1.$$ Therefore $$a(x)b(x)+c(x)+I=(\gamma^3+\gamma^2+\gamma+1)+(\gamma^2+1)=x^3+x+I.$$