How to factorize $a(y) := xy^{3}+xy^{2}+(x+1)y+x \in GF(2)[x]_{x^{2}+x+1}[y]$

Question

Could someone please help me to find irreducible factors of $a(y) := xy^{3}+xy^{2}+(x+1)y+x \in GF(2)[x]_{x^{2}+x+1}[y]$?

In $GF(2)[x]_{x^{2}+x+1}[y]$, we have $0,1,x,x+1$. So we use these in $a(y)$ one after the other: $0:x⋅0^{3}+x⋅0^{2}+(x+1)⋅0+x=x$ => not a root $1:x⋅1^{3}+x⋅1^{2}+(x+1)⋅1+x=x+x+x+1+x=4x+1=1$ => not a root $x:x⋅x^{3}+x⋅x^{2}+(x+1)⋅x+x=x^{4}+x^{3}+x^{2}+x+x=x^{4}+x^{3}+x^{2}$

But I don't understand what should I do with $x^{4}+x^{3}+x^{2}$ now? I can factorize it into $x^{2}⋅(x^{2}+x+1)$ but how can I understand that x is a root ot not?

Thank you for any help!

Answer 1

@hardmath, I'll try :-)

In $GF(2)[x]_{x^{2}+x+1}[y]$, we have $0,1,x,x+1$. So we use these in a(y) one after the other:

• $0:x⋅0^{3}+x⋅0^{2}+(x+1)⋅0+x=x$ => not a root.
• $1:x⋅1^{3}+x⋅1^{2}+(x+1)⋅1+x=x+x+x+1+x=4x+1=1$ => not a root.
• $x:x⋅x^{3}+x⋅x^{2}+(x+1)⋅x+x=x4+x3+x2+x+x=x4+x3+x2 =0$ => x is a root.
• $x+1:x⋅(x+1)^{3}+x⋅(x+1)^{2}+(x+1)⋅(x+1)+x=x+x+1+x+x=1$ => not a root.

Therefore, we know that $(y+x)$ is one of the factors.

$(xy^{3}+xy^{2}+(x+1)y+x):(y+x)=xy^{2}+y+1$

Again, we use $0,1,x,x+1$ in order to determine whether $xy^{2}+y+1$ is irreducible:

• $0:x⋅0^{2}+0+1=1$ => not a root.
• $1:x⋅1^{2}+1+1=x$ => not a root.
• $x:x⋅x^{2}+x+1=x^{3}+x+1=x$ => not a root.
• $x+1:x(x+1)^{2}+(x+1)+1=x(x^{2}+1)+x=x^{2}=1$ => not a root.

$xy^{2}+y+1$ has no roots, so it is irreducible over GF(2).

Therefore, $xy^{3}+xy^{2}+(x+1)y+x=(y+x)⋅(xy^{2}+y+1)$