¿Qué método usarías para escribir los factores primos de [matemáticas] 2 ^ {1 \, 000 \, 000} -1 [/ matemáticas] y [matemáticas] 2 ^ {1 \, 000 \, 000} +1 [ /matemáticas]? Educación te da un futuro mejor

Comenzaría con polinomios ciclotómicos.

Sin depender de ningún software especializado o del código de otra persona, podemos factorizar completamente el polinomio [matemático] X ^ {10 ^ 6} -1 [/ matemático]. Como [matemática] 10 ^ 6 = 2 ^ 6 \ veces 5 ^ 6 [/ matemática], tiene [matemática] 49 = (6 + 1) (6 + 1) [/ matemática] divisores, por lo que necesitaremos encontrar [matemáticas] 49 [/ matemáticas] polinomios ciclotómicos. Es bastante factible a mano, como lo muestro a continuación.

Un curso rápido: el polinomio [matemático] X ^ N-1 [/ matemático] puede factorizarse (sobre los números racionales) en polinomios llamados polinomios ciclotómicos. Nombre aterrador, pero son terriblemente dulces. Una forma de definirlos es ingeniosa, pero un poco misteriosa:

[matemáticas] \ Phi_d (X) = \ prod (X- \ zeta) [/ matemáticas]

donde el producto se toma sobre todas las raíces primitivas [matemáticas] d ^ {\ text {th}} [/ math] de unidad, lo que significa que cada [math] \ zeta [/ math] es un número complejo tal que [math] \ zeta ^ d = 1 [/ math] pero [math] \ zeta ^ e \ neq 1 [/ math] para todos [math] e <d [/ math].

La razón por la que esto es misterioso es que, visto de esta manera, no está del todo claro que resulten ser polinomios con coeficientes racionales y, de hecho, enteros. Pero lo hacen, y eso no es demasiado difícil de probar por inducción. Estos polinomios son irreductibles sobre los racionales, tienen coeficientes enteros y grado [matemático] \ deg \ Phi_d = \ varphi (d) [/ matemático], el número de números relativamente primos a [matemático] d [/ matemático] entre [matemático ] 1 [/ math] y [math] d [/ math].

Una forma más práctica de pensar en ellos es a través de la propiedad de factorización que mencioné:

[matemáticas] \ displaystyle X ^ N-1 = \ prod_ {d | N} \ Phi_d (X) [/ matemáticas]

Esto y la propiedad básica que [matemática] X ^ m-1 [/ matemática] divide [matemática] X ^ n-1 [/ matemática] cada vez que [matemática] m [/ matemática] divide [matemática] n [/ matemática] , te permite descubrir las [matemáticas] \ Phi_d [/ matemáticas] con bastante facilidad.

En nuestro caso, necesitamos los polinomios [math] \ Phi_d (X) [/ math] cuando [math] d [/ math] tiene la forma [math] 2 ^ i5 ^ j [/ math], ya que esos son los números que dividen [matemáticas] 10 ^ 6 [/ matemáticas]. Haciendo algunos cálculos a mano y observando los patrones (bien conocidos), podemos probar rápidamente:

[matemáticas] \ Phi_1 (X) = X-1 [/ matemáticas]
[matemáticas] \ Phi_ {2 ^ {k + 1}} (X) = X ^ {2 ^ k} +1 [/ matemáticas] para [matemáticas] k = 0,1, \ ldots, 5 [/ matemáticas]
[matemáticas] \ Phi_ {5 ^ {m + 1}} (X) = X ^ {4 \ cdot 5 ^ m} + X ^ {3 \ cdot 5 ^ m} + X ^ {2 \ cdot 5 ^ m} + X ^ {5 ^ m} +1 [/ matemática] para [matemática] m = 0,1, \ ldots, 5 [/ matemática]
[matemáticas] \ Phi_ {2 ^ {k + 1} 5 ^ {m + 1}} (X) = X ^ {4 \ cdot 2 ^ k 5 ^ m} -X ^ {3 \ cdot 2 ^ k 5 ^ m} + X ^ {2 \ cdot 2 ^ k 5 ^ m} -X ^ {2 ^ k 5 ^ m} +1 [/ matemáticas] para [matemáticas] k, m = 0,1, \ ldots, 5 [ /matemáticas]

Así que ahora, hemos factorizado completamente el polinomio [matemático] X ^ {1000000} -1 [/ matemático] sobre los racionales. Esto inmediatamente nos permite factorizar el número [math] 2 ^ {1000000} -1 [/ math], aunque desafortunadamente, no del todo.

(Nota: con el mismo método exacto puede abordar el número [matemática] 2 ^ N + 1 [/ matemática] para [matemática] N = 10 ^ 6 [/ matemática], simplemente factorizando el polinomio [matemática] X ^ { 2N} -1 = (X ^ N-1) (X ^ N + 1) [/ math]. A continuación, me centro en [math] 2 ^ N-1 [/ math]).

Cada uno de los polinomios ciclotómicos que escribimos nos da un factor de [matemáticas] 2 ^ {10 ^ 6} -1 [/ matemáticas], simplemente sustituyendo [matemáticas] X = 2 [/ matemáticas]. Estos son estos factores, organizados de acuerdo con la lista anterior, con nombres para que podamos consultarlos más adelante:

[matemáticas] 1 [/ matemáticas] (no interesante)
[matemática] a_0 = 2 ^ 1 + 1 = 3 [/ matemática], [matemática] a_1 = 2 ^ 2 + 1 = 5 [/ matemática], [matemática] a_2 = 2 ^ 4 + 1 = 17 [/ matemática] , [matemáticas] a_3 = 2 ^ 8 + 1 = 257 [/ matemáticas], [matemáticas] a_4 = 2 ^ {16} + 1 = 65537 [/ matemáticas] y [matemáticas] a_5 = 2 ^ {32} + 1 = 4294967297 [/ matemáticas].
[matemáticas] b_0 = 2 ^ 4 + 2 ^ 3 + 2 ^ 2 + 2 + 1 = 31 [/ matemáticas], [matemáticas] b_1 = 2 ^ {20} + 2 ^ {15} + 2 ^ {10} + 2 ^ 5 + 1 = 1082401 [/ matemáticas], [matemáticas] b_2 = 2 ^ {100} + 2 ^ {75} + 2 ^ {50} + 2 ^ {25} +1 [/ matemáticas], [matemáticas] b_3 = 2 ^ {500} + 2 ^ {375} + 2 ^ {250} + 2 ^ {125} +1 [/ matemáticas], [matemáticas] b_4 = 2 ^ {2500} + 2 ^ {1875} +2 ^ {1250} + 2 ^ {625} +1 [/ matemáticas] y [matemáticas] b_5 = 2 ^ {12500} + 2 ^ {9375} + 2 ^ {6250} + 2 ^ {3125} +1 [/ matemáticas ]
[matemáticas] c_ {00} = 2 ^ 4-2 ^ 3 + 2 ^ 2-2 + 1 = 11, c_ {01} = 2 ^ 8-2 ^ 6 + 2 ^ 4-2 ^ 2 + 1 = 205 [/ matemáticas], [matemáticas] c_ {02} = 2 ^ {16} -2 ^ {12} + 2 ^ 8-2 ^ 4 + 1 [/ matemáticas], [matemáticas] c_ {03} = 2 ^ { 32} -2 ^ {24} + 2 ^ {16} -2 ^ 8 + 1 [/ matemáticas], [matemáticas] c_ {04} = 2 ^ {64} -2 ^ {48} + 2 ^ {32} -2 ^ {16} +1 [/ matemáticas], [matemáticas] c_ {05} = 2 ^ {128} -2 ^ {96} + 2 ^ {64} -2 ^ {32} +1 [/ matemáticas] , [matemáticas] c_ {10} = 2 ^ {20} -2 ^ {15} + 2 ^ {10} -2 ^ 5 + 1 = 1016801 [/ matemáticas], [matemáticas] c_ {11} = 2 ^ { 40} -2 ^ {30} + 2 ^ {20} -2 ^ {10} +1 [/ math], y así sucesivamente para un total de 36 sumas de poderes alternas de [math] 2 [/ math].

El número [math] 2 ^ {10 ^ 6} -1 [/ math] es precisamente el producto de todos esos [math] a_k [/ math] s, [math] b_m [/ math] sy [math] c_ { mk} [/ matemáticas] s.

Hasta ahora, hemos logrado romper [matemáticas] 2 ^ {10 ^ 6} -1 [/ matemáticas] en [matemáticas] 48 [/ matemáticas] piezas. Lo que queda es verificar cada una de las piezas en busca de primalidad, y factorizar aún más aquellas que no son primas.

Es más fácil decirlo que hacerlo.

Aunque estos números tienen “formas” muy interesantes, no hay forma aparente de factorizarlos de manera más eficiente que los números genéricos de ese tamaño, y la mayoría de ellos tienen un tamaño que está completamente fuera del alcance de las tecnologías actuales (o, francamente, futuras). A menos que las leyes de la física sean muy diferentes de nuestra comprensión actual, o encontremos algunas formas nuevas e inteligentes de factorizar números que son sumas y diferencias de algunas potencias de [matemáticas] 2 [/ matemáticas], sospecho que nunca podremos factorizar completamente esos números.

El primer conjunto, [math] a_k [/ math] s, es fácil de manejar. Los cinco [math] a_0, a_1, \ ldots a_4 [/ math] más pequeños son todos primos, mientras que el último, [math] a_5 [/ math], no lo es, de hecho, es el primer “Fermat non- primo ”, el número que Pierre de Fermat pensó que era primo pero no lo es. Es [matemáticas] a_5 = 2 ^ {32} + 1 = 641 \ veces 6700417 [/ matemáticas].

El siguiente lote, [math] b_m [/ math] s, es sustancialmente más difícil. [matemáticas] b_0 = 31 [/ matemáticas] es primo. [math] b_1 [/ math] no es: es [math] b_1 = 601 \ times 1801 [/ math]. [math] b_2 [/ math] tampoco es primo, y es posible factorizarlo usando métodos estándar:

[matemáticas] b_2 = 269089806001 \ veces 4710883168879506001 [/ matemáticas].

El siguiente número, [math] b_3 [/ math], está en el ámbito en el que la comprobación de la primalidad sigue siendo relativamente fácil, pero la factorización no lo es. Es compuesto, pero no sé sus factores.

Así es como mostrarías que [math] b_3 [/ math] no es primo. Todo lo que necesitas hacer es calcular el residuo

[matemáticas] 3 ^ {b_3-1} \ bmod b_3 [/ matemáticas]

y verifique si el resultado es [matemática] 1 [/ matemática]. Si no, ha demostrado que [math] b_3 [/ math] es compuesto. Si resulta ser [matemáticas] 1 [/ matemáticas], el número es primo o es compuesto y eres un bastardo desafortunado. Inténtalo de nuevo con los poderes de [matemáticas] 5 [/ matemáticas], [matemáticas] 7 [/ matemáticas], [matemáticas] 11 [/ matemáticas] y así sucesivamente, y si sigues obteniendo [matemáticas] 1 [/ matemáticas], ‘ estarás muy seguro de que el número es primo. Los métodos ligeramente más elaborados le permiten demostrar que es primo, pero en nuestro caso el número es realmente compuesto y revela su composición inmediatamente después de verificar el pequeño teorema de Fermat con base [math] 3 [/ math].

Realizar este cálculo no es difícil, especialmente dada la forma simple del número [math] b_3 [/ math]. Empiezas con [matemática] 3 [/ matemática] módulo [matemática] b_3 [/ matemática] que es solo [matemática] 3 [/ matemática], y luego cuadras sucesivamente para obtener [matemática] 3 ^ 2 [/ matemática], [matemática] 3 ^ 4 [/ matemática], [matemática] 3 ^ 8 [/ matemática] y así sucesivamente, y dentro de cien pasos de cuadratura tienes [matemática] 3 ^ {2 ^ {100}} [/ matemática ] mod [matemáticas] b_3 [/ matemáticas]. Todos los cálculos se llevan a cabo utilizando mod aritmética [math] b_3 [/ math], que simplemente toma [math] 510 [/ math] bits para almacenar y manipular.

Usando el mismo método, pude demostrar que los [math] b_m [/ math] s son todos compuestos, excepto el primero, [math] b_0 [/ math]. Sin embargo, no he podido factorizarlos, y dudo que se puedan factorizar con la tecnología actual, especialmente los más grandes. [math] b_3 [/ math] puede sucumbir a ataques dedicados de varios núcleos y varios meses, pero [math] b_4 [/ math] y [math] b_5 [/ math] están completamente fuera del alcance.

Finalmente, veamos los números [math] c_ {mk} [/ math]. Una vez más, los pequeños son fáciles, los más grandes no del todo.

[matemáticas] c_ {00} = 11 [/ matemáticas]
[matemáticas] c_ {01} = 205 = 5 \ veces 41 [/ matemáticas]
[matemáticas] c_ {02} = 61681 [/ matemáticas] es primo
[matemáticas] c_ {03} [/ matemáticas] es primo
[matemáticas] c_ {04} = 414721 \ veces 4479210368001 [/ matemáticas]
[matemáticas] c_ {05} = 3602561 \ veces 94455684953484563055991838558081 [/ matemáticas]
[matemáticas] c_ {10} = 251 \ veces 4051 [/ matemáticas]
[matemáticas] c_ {11} = 5 \ veces 101 \ veces 8101 \ veces 268501 [/ matemáticas]
[matemáticas] c_ {12} = 401 \ veces 340801 \ veces 2787601 \ veces 3173389601 [/ matemáticas]
[matemáticas] c_ {13} = 1601 \ veces 25601 \ veces 82471201 \ veces 432363203127002885506543172618401 [/ matemáticas]
[math] c_ {14} [/ math] es compuesto, pero no puedo factorizarlo. (EDITAR: SageMath lo administró en aproximadamente media hora. Es [matemáticas] 3399426377632056001 \ times 4850484222084371979240001 \ times 129541188208935646963818844716591986208974410651257601 [/ matemáticas]).
[matemáticas] c_ {15} [/ matemáticas] es primo.
[matemáticas] c_ {20} = 229668251 \ veces 5519485418336288303251 [/ matemáticas]
[matemáticas] c_ {21} = 5 \ veces 7001 \ veces 28001 \ veces 96001 \ veces 3775501 \ veces 47970133603445383501 \ veces 94291866932171243501 [/ matemáticas]
[math] c_ {22} = 4001 \ times 1074001 \ times 2020001 \ times 22624001 \ times 1481124532001 \ times 8877945148742945001146041439025147034098690503591013177336356694416517527310181938001 [/ math] (tenemos muy pocos factores que son muy afortunados para tener en cuenta que este factor es muy pequeño
[math] c_ {23} [/ math] es compuesto y tiene [math] 76001 [/ math], [math] 42144001 [/ math] y [math] 293543676001 [/ math] como factores primos, pero yo no ‘ No sé cómo factorizar el resto.

Todos los demás [math] c_ {mk} [/ math] son compuestos o demasiado grandes para verificar sin más tiempo.

Esto es lo más lejos que puedo llegar. Para resumir, encontramos [matemática] 54 [/ matemática] factores primos de [matemática] 2 ^ {10 ^ 6} -1 [/ matemática], y podemos factorizar el resto en números compuestos muy grandes. El factor primo más grande que hemos encontrado es

[matemáticas] c_ {15} = 2 ^ {640} -2 ^ {480} + 2 ^ {320} -2 ^ {160} +1 [/ matemáticas]

un número con [math] 640 [/ math] dígitos binarios (o, si lo prefiere, [math] 193 [/ math] decimales). Es un factor realmente grande que habría sido muy difícil de encontrar con las técnicas genéricas de factorización, y es satisfactorio que podamos encontrarlo prácticamente a mano y demostrar que es realmente excelente.

El mayor factor probable compuesto que tenemos es

[matemática] c_ {55} = 2 ^ {400000} -2 ^ {300000} + 2 ^ {200000} -2 ^ {100000} +1 [/ matemática].

Una vez más, es realmente genial que podamos identificar un factor tan grande usando cálculos simples, aunque no parece haber ninguna forma de factorizarlo más. Las tecnologías actuales como ECM y GNFS están ridículamente lejos de poder abordar algo como esto, por lo que tendremos que dejarlo así.

¡Aunque fue divertido!