Estoy haciendo un pequeño proyecto en el ámbito de la criptografía. Recientemente me he encontrado con un problema de matemáticas relacionado con los campos finitos. Mi pregunta es cómo puedo encontrar un polinomio irreducible (o polinomio primitivo), irreducible en GF(2), con raíces linealmente independientes para un campo extendido de $GF(2^{16})$ y ¿hay algún método generalizado para encontrarlo para un tamaño de campo mayor?
Respuesta
¿Demasiados anuncios?
Esto es un poco sutil, ya que en mi solución salen a relucir propiedades relativamente especiales de este campo. Por lo tanto, no me conformaré con una pista genérica. Probablemente haya algo más sencillo. En cualquier caso, sigamos con ello.
Recordemos que la función de rastreo de $GF(2^{16})$ se define como $$ tr(x)=x+x^2+x^4+x^8+\cdots+x^{32768}=\sum_{i=0}^{15}x^{2^i}. $$ Si $F(x)=x^2$ es el automorfismo de Frobenius, entonces también podemos escribir $tr(x)=\sum_{i=0}^{15}F^i(x)$ . Recordemos también que un elemento $\alpha\in GF(2^{16})$ se dice que genera una base normal, si los elementos $\alpha, F(\alpha), F^2(\alpha),\ldots,F^{15}(\alpha)$ forman una base de $GF(2^{16})$ como un espacio vectorial sobre $GF(2)$ .
En este caso tan especial tenemos una caracterización sorprendentemente sencilla.
Lema. Un elemento $\alpha\in GF(2^{16})$ genera una base normal si y sólo si $tr(\alpha)=1$ .
Prueba. (Puede pasar por encima de tu cabeza si no estás familiarizado con la teoría de los módulos sobre PIDs) Consideramos $GF(2^{16})$ como módulo $V$ sobre el anillo polinómico $GF(2)[\tau]$ dejando que el indeterminado $\tau$ actúan como el automorfismo de Frobenius. Esto significa que si $f(x)=a_0+a_1x+\cdots a_nx^n$ es un polinomio con coeficientes en $GF(2)=\{0,1\}$ y que $v\in V$ es arbitraria, la acción del módulo es $$ f\cdot v:=\sum_{i=0}^n a_iF^i(v)=a_0v+a_1v^2+a_2v^4+\cdots+a_nv^{2^n}. $$
Se sabe que como $GF(2)[\tau]$ -Módulo $V$ es cíclico. De hecho, vemos fácilmente que $V=GF(2)[\tau]\cdot v$ si y sólo si $v$ genera una base normal. Los detalles sobre esto se incluyen en la prueba estándar de la existencia de bases normales de campos finitos. Esto se encuentra en muchos libros. Una exposición rudimentaria in situ se encuentra en mi respuesta anterior . De todos modos, observamos que la existencia de una base normal significa que $$V\cong GF(2)[\tau]/\langle \tau^{16}-1\rangle$$ como $GF(2)[\tau]$ -módulo.
Esto significa que tenemos que buscar submódulos de $GF(2)[\tau]/\langle \tau^{16}-1\rangle$ . Porque $GF(2)[\tau]$ es un PID, tales submódulos son también cíclicos y en correspondencia 1-1 con los factores de $\tau^{16}-1$ . Porque $16$ es una potencia de dos, las aplicaciones repetidas del llamado sueño del novato nos dicen que $$ \tau^{16}-1=\tau^{16}+1=(\tau+1)^{16}. $$ Esto implica que todos los factores propios de $\tau^{16}-1$ son factores de $(\tau+1)^{15}$ . En consecuencia, el único submódulo maximal de $V$ es $$ M=\{v\in V\mid (\tau+1)^{15}\cdot v=0\}. $$ La clave es que $$ (\tau+1)^{15}=\sum_{i=0}^{15}\tau^i. $$ Esto se deduce fácilmente multiplicando ambos lados por $\tau-1$ (o a partir de la expansión binomial con la ayuda de Teorema de Lucas ). En consecuencia, $$ (\tau+1)^{15}\cdot v=tr(v) $$ para todos $v\in V$ . Así, $v\in M$ si y sólo si $tr(v)=0$ .
Q.E.D.
¿Cómo te ayuda esto? Si $\alpha$ es un elemento de $GF(2^{16})$ tal que su polinomio mínimo $m_\alpha(x)$ tiene grado dieciséis, entonces $$ m_\alpha(x)=\prod_{i=0}^{15}(x-F^i(\alpha)). $$ Ampliando esto se obtiene $$ m_\alpha(x)=x^{16}+tr(\alpha)x^{15}+\text{lower degree terms}. $$
Conclusión. Encuentra un polinomio irreducible de grado 16 tal que su término de grado 15 sea distinto de cero. Entonces has terminado.
