Tenemos prueba de primalidad de Fermat para comprobar si un número es primo probable. ¿Hay una prueba análoga para los polinomios en $\mathbb{F}_{p^n}[X]$ e irreductibilidad?
Respuestas
¿Demasiados anuncios?
Parte del punto de primalidad de Fermat prueba es que $n$ es primo si y sólo si $\mathbb{Z}/(n)$ es un campo. Cuando el último es un campo, su multiplicativo grupo tiene orden de $n - 1$, por lo que cualquier representante de ${1,\dots,n-1}$ debe tener un orden dividiendo $n - 1$ mod $n$.
De forma análoga, un polinomio $f \in \mathbb{F}_q[x]$ ($q = p^n$) es irreducible si y sólo si el anillo de $\mathbb{F}_q[x]/(f)$ es un campo. El último ha pedido $q^m$, con un conjunto único de representantes está dada por los polinomios de grado estrictamente menor que $m$ (gracias al algoritmo de Euclides). Lo que si es un campo, entonces su multiplicativo grupo tiene orden de $q^m - 1$, y el orden de cada elemento se divide este valor. (Observe que cada valor distinto de cero constante polinomio tiene orden de $q-1 = |\mathbb{F}_q^*|$, el cual se divide $q^m - 1$, por lo que no habría necesidad de poner a prueba estos).
Por lo tanto me parece que la mejor analógica de primalidad de Fermat prueba sería:
- Elegir al azar un polinomio $a(x) \in \mathbb{F}_q[x]$$\deg(a)\in \{1,\dots,m-1\}$.
- Si $a^{q^m-1} \not\equiv 1 \pmod{f}$, lo $f \nmid (a^{q^m-1}-1)$, $f$ es compuesto.
David HAust
Puntos
2696
Sí, sobre campos finitos no es un polinomio irreductibilidad de la prueba de que es un eficiente analógica de la impráctico Pocklington-Lehmer entero de primalidad de prueba (véase también la Sección 3.4.3 y la Sección 8.3.1 de Henri Cohen del libro Un Curso Computacional de la Teoría Algebraica de números). La siguiente es una descripción de una forma de este algoritmo, a partir de esta página de la Wikipedia.
