¿Cómo factorizo el polinomio sobre el campo de Galois?

Question

¿Cómo funciona la factorización de polinomios sobre campos de Galois de trabajo? Me parece no puede entender el concepto básico.

Por ejemplo: ¿Cómo puedo factorizar $x^6 - 1$$\operatorname{GF}(3)$? Sé que el resultado es $(x+1)^3 (x+2)^3$, pero soy incapaz de calcular a mí mismo.

He estudiado los artículos en la Wikipedia:

• http://en.wikipedia.org/wiki/Galois_field
• http://en.wikipedia.org/wiki/Factorization_of_polynomials

pero me pareció muy difícil de entender. ¿Hay algún algoritmo que me ayudara a factorizar polinomios como $x^n - 1$$\operatorname{GF}(k)$?

Answer 1

Factorizar los polinomios$x^n - 1$ es muy diferente de factorizar polinomios generales, ya que ya sabes cuáles son las raíces; son, en una extensión finita adecuadamente grande, precisamente los elementos de orden que dividen$n$. Como sabes que el grupo multiplicativo de un campo finito es cíclico, la conclusión se sigue de aquí.

Answer 2

Si $n=pm$ es un múltiplo de a $p$ $GF(p)$ uno tiene $$x^n-1=(x^m-1)^p$$ así el problema se reduce rápidamente a los casos en que $n$ es coprime a $p$.

Si $p$ no es un factor de $n$, a continuación, a través de una clausura algebraica de $GF(p)$ $$x^n-1=\prod_{k=0}^{n-1}(x-\zeta^j)$$ donde $\zeta$ es una primitiva $n$-ésima raíz de la unidad. Uno lo hace en una factorización de la $GF(p)$ mediante la combinación de conjugar factores juntos. Para cada una de las $k$, el polinomio $$(x-\zeta^k)(x-\zeta^{pk})(x-\zeta^{p^2k})\cdots(x-\zeta^{p^{r-1}k})$$ ha coeficientes, y es irreducible sobre, $GF(p)$ donde $r$ es el menor entero positivo con $p^r k\equiv k$ (mod $n$).

El uso de este, es fácil de averiguar los grados de la irreductible factores de $x^n-1$, pero para encontrar los factores que sí necesita un poco más de de trabajo, usando, por ejemplo, el algoritmo de Berlekamp.