1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ I am sorry but i could not understand what you are asking for.. could you please a bit more preciese.. $\endgroup$
    – user87543
    Nov 30, 2013 at 16:43
  • 2
    $\begingroup$ 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)$. $\endgroup$ Nov 30, 2013 at 16:57
  • 1
    $\begingroup$ 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? $\endgroup$ Nov 30, 2013 at 17:58

1 Answer 1

1
$\begingroup$

I assume that Pablo's interpretation of your question is correct, and answer accordingly.

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

$\endgroup$

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.