¿La prueba de primalidad AKS demuestra que los primos están en P para cualquier anillo conmutativo? Si no, ¿se puede extender para hacerlo? Educación te da un futuro mejor

¡Bueno! Exploremos la complejidad computacional de las pruebas de primalidad en anillos.

Para que la pregunta “¿Son primos en P?” Tenga sentido en un anillo [matemática] R [/ matemática], primero debemos tener una representación de los elementos de [matemática] R [/ matemática] utilizando cadenas finitas de bits. No todos los anillos soportan tal representación . Por ejemplo, algunos anillos son incontables, por lo que sus elementos no pueden describirse en términos finitos, y ni siquiera podemos alimentarlos con ningún algoritmo.

Por lo tanto, la pregunta debe limitarse a anillos conmutativos contables, y para cada anillo dado debemos acordar un esquema de representación efectivo (al igual que usamos la representación binaria para enteros ordinarios, y usamos “tiempo polinómico” en referencia a la longitud de esta representación, no el tamaño del número en sí). De acuerdo, en la mayoría de los casos no importa mucho qué esquema elijamos, ya que generalmente son convertibles entre sí de manera eficiente. Pero es importante trabajar con alguna representación.

El algoritmo AKS está altamente adaptado a los enteros ordinarios. Ciertamente, no se aplica como es a otros anillos, y no está del todo claro si y cómo se puede extender a otros anillos. Sin embargo, existen anillos para los cuales la prueba de primalidad se puede reducir fácilmente al caso entero.

Examinemos algunas clases de anillos y veamos qué encontramos.

Anillos finitos

Esos son fáciles. Al igual que los innumerables anillos están fuera de discusión por simples razones de representación, los anillos finitos son obvios en la otra dirección: los elementos de un anillo finito se pueden inspeccionar en tiempo constante, y la descomposición primaria de cada elemento se puede construir en tiempo finito por búsqueda de fuerza bruta si es necesario. Entonces, la primalidad en un anillo finito es un problema trivial desde la perspectiva de la complejidad computacional.

Uno puede preguntarse qué sucede si consideramos una familia infinita de anillos finitos que tienen una estructura uniforme. Esa es una buena pregunta, pero en realidad es un millón de preguntas diferentes dependiendo de la familia que deseamos estudiar, y no la buscaré aquí, ya que hay suficientes anillos específicos para preocuparnos.

Campos

Esta es otra instancia trivial que vale la pena mencionar. En un campo, cada elemento distinto de cero es una unidad (un elemento invertible), por lo que no hay números primos y, una vez más, el problema es trivial. No hay necesidad de AKS ni de ningún otro algoritmo inteligente.

Esto se encarga de casos como los números racionales [math] \ mathbb {Q} [/ math], campos numéricos como [math] \ mathbb {Q} (e ^ {2 \ pi i / 7}) [/ math] , o los cierres algebraicos de campos finitos como [math] \ overline {{F} _ {23}} [/ math]. Los campos son demasiado fáciles.

Quizás se pregunte por qué no menciono otros campos famosos como los números reales [math] \ mathbb {R} [/ math] o los números complejos [math] \ mathbb {C} [/ math]. ¿Por qué no soy yo?

El anillo [math] \ mathbb {Z} [i] [/ math]

Antes de abordar los anillos de números enteros más generales, veamos este buen ejemplo. Este es el anillo de números de la forma [matemática] a + bi [/ matemática] donde [matemática] a, b [/ matemática] son enteros, también conocidos como enteros gaussianos. El problema de representación aquí es sencillo: representamos [math] a + bi [/ math] como un par de enteros [math] (a, b) [/ math].

¿Cómo saber si un entero gaussiano es primo? Eso es realmente bastante fácil.

Si [math] a [/ math] y [math] b [/ math] son ambos distintos de cero, [math] a + bi [/ math] es primo si y solo si [math] a ^ 2 + b ^ 2 [/ matemáticas] es primo como un entero ordinario. Por ejemplo, [matemática] 1 + i [/ matemática] y [matemática] 2 + 3i [/ matemática] son números primos, pero [matemática] 1 + 8i [/ matemática] no lo es (ejercicio: factorizarlo).
Si [matemática] a [/ matemática] o [matemática] b [/ matemática] es cero, [matemática] a + bi [/ matemática] es primo si es [matemática] \ pm 1 [/ matemática] o [matemática] \ pm i [/ math] multiplicado por un primo ordinario positivo congruente con [math] 3 [/ math] modulo [math] 4 [/ math]. Por ejemplo, [matemáticas] 7i [/ matemáticas] y [matemáticas] -19 [/ matemáticas] son números primos, pero [matemáticas] 13 [/ matemáticas] y [matemáticas] -6i [/ matemáticas] no lo son (ejercicio: factorizarlas )

Lo que esto significa es que la prueba de primalidad para enteros gaussianos no es más difícil que la prueba de primalidad para enteros. Dada la entrada [math] (a, b) [/ math], verificamos si uno de ellos es cero. Si no, probamos [matemática] a ^ 2 + b ^ 2 [/ matemática] para primalidad (usando AKS, por ejemplo), y el resultado nos dice si [matemática] a + bi [/ matemática] es. Si uno de ellos es cero, verificamos el otro por primalidad y por el residuo que deja mod [math] 4 [/ math]. Hecho.

(Observe que [math] a ^ 2 + b ^ 2 [/ math] es un número cuya representación binaria no es más del doble del tamaño de la representación de [math] (a, b) [/ math], por lo que la ejecución el tiempo de AKS sigue siendo polinomial en el tamaño de la entrada).

Entonces, aquí, AKS es ciertamente útil. No tenemos que aplicarlo a los elementos del anillo; más bien, usamos una cierta fórmula (la norma [matemáticas] a ^ 2 + b ^ 2 [/ matemáticas]) para reducir el problema al que puede manejar de forma nativa.

El anillo [math] \ mathbb {Z} [\ frac {1+ \ sqrt {-3}} {2}] [/ math]

Este es otro anillo conocido, cuyos elementos se conocen como números enteros de Eisenstein. Recientemente pasamos un tiempo de calidad con este anillo, resolviendo FLT para el caso del exponente 3.

Los números primos de Eisenstein se comportan de manera muy similar a los números primos gaussianos que acabamos de examinar. Dejando que [math] \ omega = \ frac {1+ \ sqrt {-3}} {2} [/ math], un entero de Eisenstein puede ser representado nuevamente usando un par [math] (a, b) [/ math] de enteros, correspondientes a [matemáticas] a + b \ omega [/ matemáticas]. Ese número es primo si es una unidad multiplicada por un primo común congruente con [matemática] 2 [/ matemática] módulo [matemática] 3 [/ matemática], o si su norma [matemática] a ^ 2-ab + b ^ 2 [ / math] es un primo ordinario. Entonces, una vez más, AKS muestra que la prueba de primalidad para enteros de Eisenstein está en P.

Anillos de enteros

Es tentador preguntar si los dos últimos ejemplos se generalizan al caso general de anillos de enteros. La respuesta corta es que no.

Los enteros algebraicos [math] \ mathbb {A} [/ math] son simplemente esos números complejos que son las raíces de polinomios con coeficientes enteros y coeficiente principal [math] 1 [/ math]. Raramente estudiamos su aritmética como un todo; en su lugar, nos enfocamos en un anillo numérico particular [matemática] K [/ matemática], que es una extensión finita de [matemática] \ mathbb {Q} [/ matemática], y observamos [matemática] {\ cal {O} } _K = K \ cap \ mathbb {A} [/ math].

Para tal anillo de enteros siempre hay una base integral, que es una lista finita de elementos [math] \ omega_1, \ ldots, \ omega_n [/ math] de modo que cada elemento de [math] {\ cal {O}} _ K [/ math] es una combinación lineal finita [math] m_1 \ omega_1 + \ ldots + m_n \ omega_n [/ math] de elementos básicos con coeficientes enteros.

Esto resuelve el problema de representación: un elemento de [matemáticas] {\ cal {O}} _ K [/ matemáticas] está representado por la tupla [matemáticas] (m_1, \ ldots, m_n) [/ matemáticas], tal como representamos a Gauss enteros [matemática] a + bi [/ matemática] o enteros de Eisenstein [matemática] a + b \ omega [/ matemática] como [matemática] (a, b) [/ matemática].

Sin embargo, el número suena [math] {\ cal {O}} _ K [/ math] introduce rápidamente dificultades aritméticas que no se encuentran en [math] \ mathbb {Z} [i] [/ math] o [math] \ mathbb {Z} [\ omega] [/ math].

En los enteros ordinarios, los números primos se pueden caracterizar de dos maneras distintas.

Irreducibilidad El número [math] p [/ math] es primo si es mayor que [math] 1 [/ math] y solo es divisible por [math] 1 [/ math] y en sí mismo. (Esta definición en realidad se aplica a los números naturales. Para los enteros, también debemos tener en cuenta la divisibilidad entre [math] -1 [/ math] y [math] -p [/ math]).
Primalidad El número [math] p [/ math] es primo si siempre que [math] p \ mid ab [/ math] debemos tener [math] p | a [/ math] o [math] p | b [/ math].

Para enteros ordinarios, estas dos cosas son iguales. Se mantienen igual para algunos otros anillos, pero no todos los anillos. Cuando no permanecen igual, tenemos elementos irreducibles , que satisfacen la primera definición (adecuadamente generalizada para manejar unidades), y elementos primos , que satisfacen la segunda. En los anillos de enteros (y en todos los demás dominios integrales) al menos tenemos la implicación de “cada primo es irreducible”, pero lo contrario no es necesariamente cierto.

Por lo tanto, al preguntarnos sobre la complejidad de las pruebas de primalidad en un anillo general de enteros, debemos decidir si estamos preguntando sobre las pruebas de primalidad o las pruebas de irreductibilidad.

Otra fuente de dificultad son las unidades. Las unidades en un anillo son los elementos invertibles, aquellos que tienen un inverso multiplicativo: se pueden multiplicar por algo para hacer [math] 1 [/ math]. Las unidades no son primas ni irreductibles, por lo que al menos necesitamos poder identificarlas.

En los enteros ordinarios, las únicas unidades son [math] \ pm 1 [/ math]. En los enteros gaussianos, son [math] \ pm 1 [/ math] y [math] \ pm i [/ math]. En los enteros de Eisenstein, son los seis elementos [matemática] \ pm 1 [/ matemática], [matemática] \ pm \ omega [/ matemática] y [matemática] \ pm \ omega ^ 2 = \ pm (1+ \ omega )[/matemáticas]. Esos son casos bastante leves.

Pero, en general, podemos tener infinitas unidades (de hecho, siempre tenemos infinitas unidades, excepto cuando el anillo son enteros ordinarios o el anillo de enteros de un campo de número cuadrático imaginario). La buena noticia es que podemos identificarlos algorítmicamente de manera bastante eficiente, utilizando la norma. Calcular la norma de un elemento [math] \ Sigma m_i \ omega_i [/ math] se puede hacer de manera eficiente con alguna preparación, de modo que esa parte introduce desorden pero no una complejidad computacional excesiva.

No estoy completamente seguro acerca de la complejidad computacional de las pruebas de primalidad e irreductibilidad en los campos numéricos generales. Actualizaré aquí si encuentro una respuesta definitiva.

Polinomios sobre campos finitos (variable única)

Para nuestro próximo objetivo, veremos [math] R = \ mathbb {F} _p [x] [/ math], el anillo de polinomios en una variable sobre el campo finito [math] \ mathbb {F} _p = \ mathbb {Z} / p \ mathbb {Z} [/ math]. Este campo se puede ver como el conjunto de números [matemática] \ {0,1, \ ldots, p-1 \} [/ matemática] con módulo de suma y multiplicación [matemática] p [/ matemática]. Entonces, si [matemática] p = 23 [/ matemática], un elemento típico de [matemática] R [/ matemática] puede verse como [matemática] f [x] = 17x ^ {19} + 4x ^ 8 + 20x ^ 5 + x ^ 3 + 11x ^ 2 + 2x + 4 [/ matemáticas]. El anillo [math] R [/ math] es, afortunadamente, un dominio de factorización único, por lo que nuevamente no hay diferencia entre elementos irreducibles y primos. Son uno y lo mismo.

Existen numerosas analogías entre este anillo y el anillo de enteros, y juega un papel clave en el algoritmo AKS. Sin embargo, no es necesario volver a implementar AKS para decidir la primalidad en [matemática] R [/ matemática]: las pruebas de primalidad en [matemática] R [/ matemática], y de hecho la factorización, se han sabido fáciles por mucho tiempo , al menos desde 1967 cuando Elwyn Berlekamp descubrió el algoritmo con su nombre.

El artilugio algebraico clave que hace que [math] R [/ math] sea más manejable que [math] \ mathbb {Z} [/ math] es el endomorfismo de Frobenius , el mapa [math] x \ mapsto x ^ p [/ math]. Este mapa es trivial en [math] \ mathbb {F} _p [/ math] en sí mismo, pero en cualquier extensión de este campo se encuentra en el corazón de un millón de algoritmos, teoremas y resultados en álgebra y análisis.

En resumen, el algoritmo de Berlekamp funciona de la siguiente manera. Dado un polinomio [matemático] f (x) \ en R [/ matemático] de grado [matemático] n [/ matemático], primero calculamos el mcd de [matemático] f [/ matemático] y su propia derivada [matemática] f ‘[/matemáticas]. Esto establece rápidamente si [math] f [/ math] es cuadrado, lo que significa que no tiene factores repetidos; si ese no es el caso, [math] f [/ math] definitivamente no es primo. Calcular la derivada es trivial, y calcular los mcd en [math] R [/ math] es tan fácil y eficiente como calcularlos en [math] \ mathbb {Z} [/ math], utilizando el algoritmo euclidiano.

Luego calculamos, para cada [matemática] k [/ matemática] entre [matemática] 0 [/ matemática] y [matemática] n-1 [/ matemática], los residuos

[matemáticas] x ^ {pk} \ equiv a_ {k, n-1} x ^ {n-1} + a_ {k, n-2} x ^ {n-2} + \ ldots + a_ {k, 1 } x + a_ {k, 0} \ pmod {f (x)} [/ math]

Los elementos de campo [math] a_ {i, j} [/ math] están dispuestos en una matriz cuadrada, y esta matriz se puede usar para factorizar [math] f [/ math]. En particular, tiene rango [matemáticas] n-1 [/ matemáticas] si y solo si [matemáticas] f [/ matemáticas] es irreducible (en general, tiene rango [matemáticas] nk [/ matemáticas] si [matemáticas] f [/ math] tiene [math] k [/ math] distintos factores primos). Las matrices de triangulación se pueden hacer en tiempo polinómico, por lo que todo este algoritmo requiere operaciones [matemáticas] O (n ^ 2) [/ matemáticas] o más o menos.

Como es común aquí, consideramos que las operaciones aritméticas en [math] \ mathbb {F} _p [/ math] toman tiempo constante; en realidad, toman [math] \ log (p) [/ math] tiempo, pero podemos ignorar esto ya que el anillo [math] R [/ math] y [math] p [/ math] son fijos y el comportamiento asintótico es con respecto al grado [matemático] n [/ matemático] del polinomio. (En la práctica, existen algoritmos más eficientes para este problema, como Cantor-Zassenhaus, que también son mejores para manejar primos grandes [math] p [/ math]).

Los anillos [math] \ mathbb {Z} [x] [/ math] y [math] \ mathbb {Q} [x] [/ math]

Factorizar polinomios sobre los racionales y sobre los enteros es esencialmente lo mismo, debido al lema de Gauss. Es un hecho altamente trivial que factorizar en [math] \ mathbb {Z} [x] [/ math] se puede hacer en tiempo polinómico. En consecuencia, la prueba de primalidad también se puede hacer en tiempo polinómico. No conozco una forma más rápida de mostrar que un polinomio con coeficientes enteros es irreducible, aparte de aplicar un algoritmo de factorización completo.

Arjen Lenstra, Hendrik Lenstra y László Lovász [1] crearon en 1982 el primer algoritmo determinista de tiempo polinómico para factorizar polinomios de variable única sobre los enteros o racionales, como consecuencia de su famoso algoritmo de reducción de celosía “LLL”. En términos del grado [matemático] n [/ matemático] del polinomio a factorizar, y la norma euclidiana [matemática] E [/ matemático] del vector de coeficiente del polinomio, el tiempo de ejecución es [matemático] O (n ^ {12} + n ^ 9 \ log (E) ^ 3) [/ math]. Este es un grado bastante alto para un algoritmo de tiempo polinómico, pero ciertamente es tiempo polinómico.

La idea central es esta. Si [math] f = gh [/ math] es reducible, entonces [math] \ bar {f} = \ bar {g} \ bar {h} [/ math] es una factorización de la reducción de [math] f [ / math] módulo [math] p [/ math], para cualquier primo [math] p [/ math]. Entonces, si desea factorizar un polinomio sobre los enteros, es natural elegir primos aleatorios [matemática] p [/ matemática], reducir [matemática] f [/ matemática] mod [matemática] p [/ matemática] y factorizar el reducción [matemática] \ bar {f} [/ matemática] usando el algoritmo de Berlekamp. Si encuentra una factorización para alguna [matemática] p [/ matemática] particular, puede usar el lema de Hensel para elevarla a una factorización adica [matemática] p [/ matemática]; la pregunta es si este factor puede convertirse en un factor genuino sobre [math] \ mathbb {Z} [/ math]. Es este problema que Lenstra, Lenstra y Lóvász resuelven ingeniosamente utilizando reducciones de celosía.

Obviamente, hay muchos otros anillos para explorar. Esta breve encuesta puede servir, al menos, para ilustrar un par de puntos clave: diferentes anillos requieren métodos radicalmente diferentes, y el algoritmo AKS es útil cuando logramos reducir un problema a [math] \ mathbb {Z} [/ math] , pero por lo demás no es directamente aplicable a otros anillos contables.

Notas al pie

[1] https://www.math.leidenuniv.nl/~…