# elegant way to show $P= t^{1024}+t+1$ is reducible in $\mathbf{F}_{2}[t]$

This is homework exercise: $$P=t^{1024} + t + 1 , R = \mathbf{F}_{2}[t] \Rightarrow P \ \text{reducible in R}$$

I wanted to show this analogous to how a book shows it (book shows it with other numbers and field): $a^{1024}= a+1$ has solutions in $R/PR$, then calculate $a^{2^{20}}, a^{2^{1024}}$ in $R/PR$ and by using gcd conclude that P is reducible over R.

My problem is that the numbers are so big that I can't split up and show that there are solutions or calculate $a^{2^{20}}, a^{2^{1024}}$ in $R/PR$. But there must be an easy way since it is homework. So how to show that $a^{1024} = a+1$ is solvable in $R/PR$ and how to compute $a^{2^{20}}, a^{2^{1024}}$ in $R/PR$? Thanks for all input.

-
By brute force: $t^4+t+1$ divides $P.$ – user2468 Dec 22 '11 at 12:45
Thanks for your comment. Is there no way to show it the way the book does it? Because I can't brute force in the exam. – Tashi Dec 22 '11 at 12:51
$a^{1024}=a+1$ is automatically solvable in $R/PR$, and a root is the residue of $t$. Seeing why this is true is a good test of your understanding of the definition of $R/PR$. If it is not clear why $a^{1024}=a+1$ has a root in $R/PR$, spend some time with the definition of $R/PR$. – Ben Blum-Smith Dec 22 '11 at 13:10
@Ben: i find patronizing comment with zero math content not specialy usefull. – evgeniamerkulova Dec 22 '11 at 16:07
@evgeniamerkulova: Tashi can judge for self but I certainly wasn't feeling patronizing when I wrote it. Was trying to give good advice. If not clear why $a^{1024}=a+1$ is solvable in $R/PR$, definition of $R/PR$ is right place to start. – Ben Blum-Smith Jan 10 '12 at 1:41

In $\mathbb{F}_{16}$ which is isomorphic to $\mathbb{F}_2[x]/(x^4+x+1)$ exists an Element $y$ which is a root of $x^4+x+1$ (obviously). Since $\Phi:\mathbb{F}_{16} \rightarrow \mathbb{F}_{16}: z \mapsto z^2$ has Order $4$ as an automorphism we get that $y^{1024}=\Phi^{10}(y)=\Phi^2(y)=y^4$ and therefore $y^{1024}+y+1=y^4+y+1=0$.

Using this you should be able to show reducibility.

-
Is this what your way continues: $gcd(t^{1024}+t+1,t^{16}-t)$, and from this it concludes that it is reducible? Thank you. – Tashi Dec 22 '11 at 13:27
This is one possibility. You could also use the fact that $f=x^4+x+1$ is the minimal polynomial of y. Therefore f divides every polynomial (over $\mathbb{F}_2$) that has y as a root. – Sebastian Schoennenbeck Dec 22 '11 at 13:38
What amounts to more or less the same thing is the observation that $y^{15}=1$ (Lagrange's theorem in the group $F_{16}^*$). As $15\mid 1020$ we then get that $y^{1020}=1$, and hence $y^{1024}=y^4$. – Jyrki Lahtonen Dec 22 '11 at 14:59

An answer based on J.D.'s hint (and essentially equivalent to Sebastian's excellent solution):

Let $r(t)=t^4+t+1$. Then $r(t)^{4^i}=t^{4^{i+1}}+t^{4^i}+1$ for all $i$. Therefore \begin{aligned} r(t)+&r(t)^4+r(t)^{16}+r(t)^{64}+r(t)^{256}=\\&=5\cdot1+(t+t^4+t^{16}+t^{64}+t^{256})+(t+t^4+t^{16}+t^{64}+t^{256})^4\\&=1+t+t^{1024}.\end{aligned} But clearly the l.h.s. is divisible by $r(t)$, so is the r.h.s., and hence it cannot be irreducible. Not really brute force, but not entirely obvious, unless you have spent some time with finite fields.

Yet another way, but not the recommended way :-), of proving the claim is the following. We know that $q(t)=t^{1024}+t$ has the property that $q(u+v)=q(u)+q(v)$ for all $u,v$ in an algebraic closure of $F_2$. But we also know that $q(u)=0$ if and only if $u\in F_{1024}$. Now if we assume contrariwise that $P(t)$ is irreducible, and $y$ is one of its roots, then $y$ would generate the field $F_{2^{1024}}$. This field is Galois over $F_2$, so it must contain all the roots of $P(t)$ (being a normal extension). But the earlier observations imply that all the elements of the form $y+u$, with $u\in F_{1024}=F_{2^{10}}$ must also be zeros of $P(t)=q(t)+1$, because $$P(y+u)=q(y+u)+1=q(y)+q(u)+1=q(y)+1=P(y)=0.$$ Thus also $u=(y+u)+y$ belongs to the splitting field $F_{2^{1024}}$ of $P(t)$. Here $u\in F_{2^{10}}$ was arbitrary, so $F_{2^{10}}\subseteq F_{2^{1024}}$. But this is a contradiction, because $10\nmid 1024$.

This kind of manipulations are not uncommon when playing with linearized (and affine) polynomials in $F_p[t]$, i.e. polynomials with terms of degrees that are powers of $p$ only.

-
A more general result along J.D.'s hint would read: If $m$ is an odd number, then $1+t+t^{2^n}$ is a factor of $1+t+t^{2^{nm}}$ in the ring $F_2[t]$. Here $n=2$, $m=5$. – Jyrki Lahtonen Dec 22 '11 at 15:38