Descomposición en factores cierto polinomio como $x^{10}-1$ eficiente

Question

Quiero saber:

¿Hay una manera eficiente de factorizar polinomios como

$$x^{10}-1~~~,\text{or}~~~x^{16}-x$$ over small finite fields like $ F_2$ and $ F_3 $ por ejemplo?

¿Cómo lo harías tú? Quiero ver algunas técnicas que puedo aplicar a otros polinomios de este tipo. Gracias:)

Answer 1

En general, la factorización de un polinomio de la forma $x^n-1$ $\Bbb{F}_p$ es aproximadamente equivalente a la producción de listas de polinomios irreducibles sobre $\Bbb{F}_p$. Esto es debido a que todos los polinomios irreducibles $p(x)$$\Bbb{F}_p$, con la excepción de $p(x)=x$ se producen como factores (ver el comentario abajo).

De todos modos, las siguientes cosas son fáciles de ver:

1. Si $n=p^km$$p\nmid m$, luego $$x^n-1=(x^m-1)^{p^k}.$$ Therefore it suffices to study the case $p\nmid$n.
2. La característica cero de la factorización en cyclotomic polinomios todavía cuenta con más de $\Bbb{F}_p$: $$x^n-1=\prod_{d\min n}\Phi_d(x).$$ The difference is that the polynomials $\Phi_d(x)$ are no longer irreducible in general modulo $p$.
3. El uso de la teoría de Galois de las extensiones de campos finitos es fácil ver que cuando se $p\nmid n$, los factores de $\Phi_n(x)$ modulo $p$ todos tienen el mismo grado $f$ donde $f$ es el menor entero positivo con la propiedad $n\mid p^f-1$. En otras palabras $f$ es el orden de la coset de $p$ en el grupo multiplicativo $\Bbb{Z}_n^*$. Esto ha sido explicado muchas veces en nuestro sitio (pregunte si usted no puede encontrar ese hilo).

Sin embargo, la búsqueda de la persona irreductible factores de cyclotomic polinomios $\Phi_n(x)$ $\Bbb{F}_p$ no es sencillo. Hay trucos, y si no hay es el algoritmo de Berlekamp. Demasiado largo para caber aquí.

Answer 2

El resto de los casos, más de $\mathbb{F}_3$ están dadas por $$ x^{10}-1=(x^4 + 2x^3 + x^2 + 2x + 1)(x^4 + x^3 + x^2 + x + 1)(x + 2)(x + 1), $$ y $$ x^{16}-1=(x^4 + 2x^2 + 2)(x^4 + x^2 + 2)(x^2 + 2x + 2)(x^2 + x + 2)(x^2 + 1)(x + 2)(x + 1). $$ Los lineales de los factores son fáciles de encontrar, pero para los otros factores que uno tiene que hacer más. El resultado muestra que tenemos algunos métodos generales, y hay muchos de ellos (en particular Berlekamps del algoritmo), ver aquí.

Answer 3

$F_2$:\begin{gather*} x^{10}-1=x^{10}+1=(x^5+1)^2=((x+1)(x^4+x^3+x^2+x+1))^2=(x+1)^2(x^4+x^3+x^2+x+1)^2. \end{Frunce *}

Answer 4

$F_2$ Tenemos $x^{16}-1=x^{16}+1=(x^8+1)^2=(x^4+1)^4=(x^2+1)^8=(x+1)^{16}.$ $F_{p^n}$ $p$ es primer, dos polinomios son iguales si sus correspondientes coeficientes son congruentes modulo $p$.

Answer 5

Un hecho interesante que cubre el $x^{16}-x$ $\mathbb{F}_2$ caso es el siguiente:

$\mathbb{F}_{q}$, El polinomio $x^{q^n}-x$ es el producto de polinomios irreducibles monic todos $\mathbb{F}_q$ cuyo grado divide $n$.

Así $\mathbb{F}_2$, $x^{16}-x$ es el producto de polinomios irreducibles monic todos $\mathbb{F}_2$ $1,2, \text{ and } 4$ de grado.