% Mínima $n$de un polinomio a dividir $x^n-1$

Question

Decir que tengo un determinado polinomio $g(x)$ en el campo $\mathbb Z_2 $. ¿Cómo puedo encontrar el % mínimo $n$que $g(x)|x^n-1$?

Por ejemplo, me dijeron que para cualquier $n<32768$ $g(x)=x^{15}+x^{14}+1$ no divide $x^n-1$ (tengo detectado que $2^{15}=32768$, sin embargo no sé cómo hacer esta relación). ¿Cómo se llega a esta conclusión?

Gracias.

Answer 1

Esto es un poco de una respuesta parcial.

Supongamos, como en el ejemplo concreto, que $g(X)$ es coprime a $X$ e irreductible.

Deje $t=deg(g)$. Desde $g(X)$ es irreductible, contigua a la de cualquiera de sus raíces genera el campo exclusivo de grado $2^t$$\mathbb{F}_2$, es decir,$\mathbb{F}_{2^t}$. Ya que esta es también conocido por ser el conjunto de raíces de $X^{2^t}-X$,$g(X)|X^{2^t}-X$. Por lo tanto, siempre es cierto que $g(X)|X^{2^{deg(g)}-1}-1$.

Por otro lado, es bien sabido que $gcd(X^n-1,X^m-1)=X^{gcd(m,n)}-1$. Por lo tanto, la mínima polinomio de la forma $X^n-1$ que $g$ divide a ha $n\mid2^{deg(g)}-1$.

En general, creo que no podemos hacer nada mejor que esto: teniendo en cuenta las raíces de $g(X)$ como los elementos de la cíclico grupo $\mathbb{F}_{2^{deg(g)}}$, todos ellos tienen el mismo orden, ya que son conjugados a través de Frobenius, y $2$ es el primer a $\#\mathbb{F}_{2^{deg(g)}}^{\times}$. Por lo tanto, por ejemplo, saber si este mínimo $n$ $2^{deg(g)}-1$ es como saber si las raíces de $g(X)$ son los generadores del grupo multiplicativo. No sé, en general, de manera de responder a esta pregunta sin comprobar esto de forma explícita para el polinomio.

Así, en el ejemplo, $g(X)$ divide $X^{2^{15}-1}-1$, y comprueba que no se divida cualquier potencia inferior sólo se necesita comprobar que el $X^{m}-1\neq 0 (\text{ mod } g(X))$ $m\neq 2^{15}-1$ dividiendo $2^{15}-1$.

Answer 2

Esto se siente como que podría ser útil para pensar acerca de la división de campo de la $g(x)$$\mathbb{F}_2$.

Mediante el uso de algunas de la teoría de Galois, usted puede demostrar que no existe un solo campo de orden de $q=p^k$ para algunos prime $p$ y un entero positivo $k$, hasta isomorfismo. También, la no-cero elementos de $\mathbb{F}_q$ formar un multiplicativo cíclico grupo. Esto significa que no son cero los elementos de la $\mathbb{F}_q$ satisfacer $X^{q-1}-1$.

Esto significa que si la división de campo de la $g(X)$$\mathbb{F}_{q}$, $g(x)$ divide $X^{q-1}-1$$\mathbb{F}_p$, ya que las raíces de $g(x)$$\mathbb{F}_{q}$.

En cuanto a por qué $g(X)$ no divide a una potencia más baja,estoy de acuerdo con Gal Porat es comprobar a través de los divisores de a $2^{15}-1$. Aunque, sólo para reiterar que usted no tiene que comprobar $2^3-1$ o $2^5-1$ porque si $g(X)$ hizo dividir, entonces la división de campo sería de $\mathbb{F}_{2^5}$ $\mathbb{F}_{2^3}$ en lugar de $\mathbb{F}_{2^{15}}$.