Estoy tomando todos los polinomios irreducibles sobre $\mathbf{F}_2$ de grado 1 a 4, ambos inclusive y el uso de la división larga para determinar si los $f$ es divisible por ninguno de ellos y no es así.
¿Cuáles son las otras maneras?
Respuesta
¿Demasiados anuncios?
Esto se puede hacer rápidamente por el algoritmo de Euclides. Si $f$ es reducible tiene un factor irreducible de grado $\le 4,\,$, por lo tanto se tiene un factor en común con $\, x^{16}-x\,$ (que es divisible por cada irreducible de grado dividiendo $4$) o, tiene cúbicos factor, por lo tanto, un factor en común con $\,x^8-x,\,$ por lo tanto un factor en común con $\, g =x^7-1,\,$ desde $\,x\nmid f.\,$
El último caso es imposible, ya que $\,f\ {\rm mod}\ g = f - (x+1)(x^7\!-1) = x^3,\,$ $\,(f,g) = (f\ {\rm mod}\ g,\,g) = (x^3,g) = 1\,$ $\,(x,g)= (x,x^7\!-1) = (x,-1)= 1.$
Para el primer caso, por $\,x\nmid f,\,$ es suficiente para mostrar que el $\,f\,$ es coprime a $\,g = x^{15}\!-1.$
División de $ $ rendimientos $\ \ g\ {\rm mod}\ f = x^6\!+x^4\!+x^2 = x^2 h^2,\ \ h = x^2\!+x+1 $
Por lo tanto $\ \ (g,f) = (g\ {\rm mod} f,\, f) = (x^2 h^2,f)$, por lo que es suficiente para mostrar $(h,f) = 1,\ $ desde $\,x\nmid f$.
De hecho,$\,(h,f) = (h,\, f\ {\rm mod}\ h) = (h,x\!-\!1) = (h(1),x\!-\!1)=(1,x\!-\!1)=1$.
