I am taking all the irreducible polynomials over $\mathbf{F}_2$ of degree 1 to 4 inclusive and using the long division to determine whether the given $f$ is divisible by anyone of them and it is not so.
What are the other ways?
$\begingroup$
$\endgroup$
5
-
5$\begingroup$ Your method may well be the best way. The only other thing that comes to mind is to show (compute) $gcd(f, x^{16}-x) = 1$, as every irreducible polynomial of degree dividing dividing $4$ over $\mathbb{F}_{2}[x]$ divides $x^{16}-x$. Then you can check the remaining irreducible polynomials of degree $3$, but that's all that I can think of. $\endgroup$– Alex WertheimDec 29, 2013 at 22:22
-
1$\begingroup$ Agree with AWertheim. If you want to check both irreducible cubics in one go, you can similarly calculate $\gcd(f,x^8-x)$. Here $f-(x^8+x)=x^7+x^3+1$ that I recognize as my favorite low weight primitive (hence irreducible) polynomial of degree 7, so it is already clear that $\gcd(f,x^8-x)=1$. $\endgroup$– Jyrki LahtonenDec 29, 2013 at 22:46
-
$\begingroup$ There are immediate observations that would speed up checking divisibility by irreducible quartics: $x^{5+n}+x^n$ is divisible by the fifth cyclotomic, so $f$ has a quadratic remainder $f+(x^3+x^2)(x^5+1)$ modulo $x^4+x^3+x^2+x+1$. Similar "pattern matching" shows right away that $f+(x^4+1)(x^4+x^3+1)=x$ and $f$ being almost palindromic simplifies checking non-divisibility by the reciprocal $x^4+x+1$ a bit. The quadratic irreducible is a factor of $x^3+1$, but both $x^3+1$ and $x^7+x=x(x^6+1)$ are divisible by that... $\endgroup$– Jyrki LahtonenDec 29, 2013 at 22:55
-
$\begingroup$ There’s no problem with irreducible cubic factors, is there? If such a polynomial divided $f$, then its root $\rho$ (a primitive seventh root of unity) would be a root of $f$. But then $\rho^8+\rho^7+\rho+1=0$, and $f(\rho)=\rho^3\ne0$. $\endgroup$– LubinDec 30, 2013 at 0:21
-
$\begingroup$ Correct, @Lubin. I noticed that after it was a bit too late to fix the comment. And I also knew that particular irreducible heptic :-). Well, Bill Dubuque seems to have handled it that way as well, and it is admittedly a better way. $\endgroup$– Jyrki LahtonenDec 30, 2013 at 13:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This can be done quickly by the Euclidean algorithm. If $f$ is reducible it has an irreducible factor of degree $\le 4,\,$ so either it has a factor in common with $\, x^{16}-x\,$ (which is divisible by every irreducible of degree dividing $4$) or, it has cubic factor, hence a factor in common with $\,x^8-x,\,$ hence a factor in common with $\, g =x^7-1,\,$ since $\,x\nmid f.\,$
The latter case is impossible, since $\,f\ {\rm mod}\ g = f - (x+1)(x^7\!-1) = x^3,\,$ thus $\,(f,g) = (f\ {\rm mod}\ g,\,g) = (x^3,g) = 1\,$ by $\,(x,g)= (x,x^7\!-1) = (x,-1)= 1.$
For the first case, by $\,x\nmid f,\,$ it suffices to show that $\,f\,$ is coprime to $\,g = x^{15}\!-1.$
Division $ $ yields $\ \ g\ {\rm mod}\ f = x^6\!+x^4\!+x^2 = x^2 h^2,\ \ h = x^2\!+x+1 $
Hence $\ \ (g,f) = (g\ {\rm mod} f,\, f) = (x^2 h^2,f)$ so it suffices to show $(h,f) = 1,\ $ since $\,x\nmid f$.
Indeed $\,(h,f) = (h,\, f\ {\rm mod}\ h) = (h,x\!-\!1) = (h(1),x\!-\!1)=(1,x\!-\!1)=1$.
answered Dec 30, 2013 at 0:08