¿Hasta qué punto se sabe que la lista de primos conocidos está completa?

Question

Así que siempre queda la búsqueda del siguiente "mayor número primo conocido". El último resultado que salió de GIMPS fue $2^{74\,207\,281} - 1$ con más de veinte millones de dígitos. Wikipedia también enumera los veinte números primos más altos conocidos, sólo los cuatro más pequeños de esa lista tienen menos de tres millones de dígitos.

Hace tiempo que me pregunto por los números primos más pequeños que no hemos encontrado. ¿Hasta qué punto se sabe que la lista de primos conocidos está completa? Desde $500$ a $1000$ dígitos se consideran seguros para el algoritmo RSA, yo asumiría que está muy por debajo de eso. ¿A qué distancia de la línea numérica hemos comprobado que no hay más primos que encontrar? ¿A qué velocidad avanza este límite, actualmente? ¿Hemos comprobado, por ejemplo, la primalidad de todos los números por debajo de $10^{100}$ o estamos atascados en algún lugar al sur de $10^{20}$ ?

Answer 1

El máximo de dicha lista es lejos más pequeños que los mencionados 500 dígitos. Debido al teorema del número primo $\pi(x) \approx x/\log(x)$ por lo que se podría estimar que la lista de números primos hasta $x$ requeriría del orden de $x$ dígitos para representar.

Por lo tanto, al utilizar el tamiz de Atkin la complejidad es $O(x)$ tanto por el consumo de tiempo como por el consumo de memoria. Y toda la memoria disponible es lo suficientemente pequeña como para que sea factible recorrerla. Esto significa que la memoria disponible para almacenar dicha lista es lo que debería ser el factor limitante.

Básicamente, esto se reduce a que la lista más grande de este tipo es tan grande como cualquiera tiene lugar (y necesidad).

Ahora se estima que el almacenamiento global total es del orden de $10^{21}$ bytes lo que significa que el límite superior de dicha lista de números primos está ahí. Así que no existe una lista completa con números primos de más de veinte dígitos (y ni siquiera eso, ya que no todo el almacenamiento se dedica a almacenar números primos).

Answer 2

Puede ser una respuesta poco satisfactoria, pero nadie tiene una lista completa de los primos conocidos (que yo sepa). Además, es bastante fácil encontrar números primos grandes, y es bastante fácil "garantizar" (garantizar es un término resbaladizo), que un número grande dado es primo.

El Prueba de primalidad de Miller-Rabin es un algoritmo que toma un número $n$ , y un parámetro de "certeza" $m$ y (en términos sencillos) si $n$ es primo, devolverá "PRIME". Si $n$ es compuesto, es casi seguro (de nuevo, un término resbaladizo) que devolverá "COMPOSITE", pero hay una pequeña probabilidad $(\frac{1}{4^m})$ que devolverá "PRIME".

Sin embargo, al establecer $m$ lo suficientemente alto, a, digamos, algo mayor que 40, entonces significa esencialmente que la probabilidad de que un número compuesto sea declarado primo es menor que la de ganar el premio gordo de la lotería dos veces en una semana. Así, para casi TODOS los fines prácticos, basta con trabajar con primos que pasen la prueba de Miller-Rabin con un alto grado de certeza. Henri Cohen llamó a estos números "primos de grado industrial".

Si todavía estás interesado en tener una "prueba" de que un número es primo, te sugiero que leas sobre certificados de primera calidad . Sin embargo, nunca me he encontrado con una situación en la que se prefiera una imprimación certificada a una imprimación de grado industrial.

Finalmente, como ejemplo rápido, Mathematica puede generar primos muy grandes fácilmente. El comando de Mathematica "RandomPrime[{10^1000, 10^1001}]" genera un primo aleatorio de 1000 dígitos en 0,40625 segundos en mi máquina de escritorio de cinco años. Esto debería darle alguna indicación de por qué los matemáticos generalmente no mantienen largas listas de todos los primos conocidos.

Answer 3

Parece que este enlace , proporcionado por Yuriy S en los comentarios anteriores responde más o menos a mi pregunta. Afirma que las búsquedas de huecos primos han comprobado la primalidad (pero no han almacenado los primos) de todos los números hasta unos 20 dígitos (el límite exacto siempre cambia, ya que los números son relativamente pequeños).

Answer 4

Enumerar los primos en orden es una tarea bastante trivial problema - de hecho, creo que tenemos programas que pueden calcular listas de primos más rápido de lo que se puede escribir en el disco, y mucho menos se muestra en cualquier formato legible para el ser humano.

La cuestión es que hay un lote de los primos. Todo Internet junto probablemente no podría almacenar la lista de todos los primos de 20 dígitos.

Pero no pasa nada, porque no necesitamos listas de números primos: siempre que necesitemos números primos, podemos generarlos.