Solución:
Según un artículo “Polinomios irreductibles óptimos para $ GF (2 ^ m) $ aritmética” de M. Scott, “en la práctica siempre es posible elegir como polinomio irreducible un trinomio … o un pentanomio”. [talk slides] [PDF link]
En los generadores de números aleatorios, los trinomios irreductibles de varios grados con tres coeficientes binarios distintos de cero se asocian con los nombres Tausworthe-Lewis-Payne.
Adicional: Se sabe desde Gauss que hay muchos polinomios irreducibles sobre un campo finito, básicamente el análogo del Teorema de los números primos para tales polinomios. Entre los polinomios $ 2 ^ m $ (monic) sobre Z / 2Z de grado $ m $, aproximadamente $ 1 / m $ de ellos son irreducibles.
Podemos eliminar la posibilidad de factores de primer grado mediante inspección, ya que la divisibilidad por $ x $ o $ x + 1 $ implicaría, respectivamente, un término constante cero o un número par de términos distintos de cero en el polinomio. Entonces, el primer caso para probar la irreductibilidad son los trinomios de grado $ m $. Con coeficientes iniciales y constantes que representan dos de los tres términos distintos de cero, hay solo $ m-1 $ posibilidades para probar, y por simetría de sustitución $ x $ → $ 1 / x $, podemos restringir los términos medios a un grado ≤ $ m / 2 $.
Si ninguno de ellos funciona, tenemos el suministro más rico de pentanomios para probar. De hecho, parece que ha encontrado una serie de casos en los que los trinomios nunca funcionarán, es decir, grado $ m $ múltiplo de 8 [PS] (Swan, 1962).
El trabajo luego se reduce a probar todos los $ binom {m-1} {3} $ pentanomios binarios $ p (x) $ hasta que encontremos uno que sea irreductible. Su solicitud puede hacer que otras condiciones, tal vez similares a las consideradas en el artículo de Scott anterior, sean atractivas. Dados los grados modestos con los que está trabajando, la división de prueba (tomando $ p (x) ; mod ; q (x) $ para todos los $ q (x) $ de grado ≤ $ m / 2 $) debería ser lo suficientemente rápida. [Remember, we shouldn’t have to test more than O(m) possibilities before we find success.]
Hay una forma más elegante [PDF] para probar polinomios para determinar la irreductibilidad sobre GF (2). A necesario La condición para que el polinomio binario $ p (x) $ sea irreducible sobre $ GF (2) $ es que:
$$ x ^ {2 ^ m} = x mod p (x) $$
De hecho, Gauss demostró para q primo que $ x ^ {q ^ m} – x $ es precisamente el producto de todos los polinomios mónicos irreducibles sobre $ GF (q) $ cuyos grados dividen $ m $. [From this he deduced the count of monic irreducible polynomials of
degree exactly $m$ is asymptotically $q^m/m$ as $m rightarrow infty$.]
Para $ q = 2 $ se deduce que si $ p (x) $ es irreductible de grado $ m $, divide $ x ^ {2 ^ m} – x $ sobre $ GF (2) $, es decir, la congruencia anterior.
Rubin (1980) propuso una prueba necesaria y suficiente de irreductibilidad, combinando lo anterior con algunos pasos adicionales para descartar la posibilidad de que $ p (x) $ pudiera ser el producto de algunos factores irreducibles cuyos grados dividen adecuadamente $ m $. [While the degrees of the irreducible factors would
naturally sum to $m$, having all the irreducible factors’ degrees divide
$m$ would be somewhat special, unless of course there is only one factor.]
Los pasos adicionales de “suficiencia” son para verificar cada principal factor $ d_i $ de $ m $ que: $$ GCD (x ^ {2 ^ {m / d}} – x, p (x)) = 1 $$
Es decir, si $ p (x) $ tuviera un factor irreducible de grado $ k $ que dividiera correctamente $ m $, aparecería al tomar el mcd de $ x ^ {2 ^ {m / d}} – x $ y $ p (x) $ si $ k $ divide $ m / d $.
Desde entonces, se ha aplicado mucho ingenio para realizar estos pasos de manera eficiente. Por supuesto, la condición necesaria se presta a cuadratura repetida, calculando $ x ^ {2 ^ {k + 1}} = (x ^ {2 ^ k}) ^ 2 $ mod $ p (x) $, para $ k $ hasta $ m-1 $. Podemos aprovechar aquí el hecho de que la multiplicación que estamos haciendo es un cuadrado y la ventaja de la escasez de nuestro $ p (x) $ como pentanomio al hacer el mod de reducción $ p (x) $.
Como señala el informe de Brent sobre el trabajo con Zimmerman (vinculado arriba), esta cuadratura repetida da con cada paso (paso bastante económico) un progreso lineal hacia el “exponente del exponente” $ m $. También hay una manera de progresar más con un mayor esfuerzo computacional al composición modular.
Es decir, supongamos que ya llegamos a: $$ f (x) = x ^ {2 ^ k} mod p (x) $$ y $$ g (x) = x ^ {2 ^ j} mod p (x) $$ Entonces: $$ f (g (x)) = x ^ {2 ^ {k + j}} mod p (x) $$
Por lo tanto, la composición de dos polinomios $ f (x) $ y $ g (x) $ mod $ p (x) $ puede reemplazar varios pasos de cuadratura repetidos. Pero la composición mod $ p (x) $ es más cara que el cuadrado o incluso que la multiplicación generalmente mod $ p (x) $. Entonces, como señala Brent, la ventaja práctica de usar la composición modular se encuentra en la etapa final de la evaluación de la condición necesaria. Por ejemplo, al final, una composición modular podría reemplazar $ m / 2 $ escuadrados repetidos.
En cuanto a las condiciones de “suficiencia”, Gao y Panario describieron una mejora con respecto a una implementación ingenua de las pruebas de Rubin en este artículo de 1997. [PDF], básicamente secuenciando los cálculos del gcd en un orden conveniente.