Así, recientemente se ha encontrado un número primo absurdamente grande, pero todavía no se conocen muchos números primos menores que él. Me pregunto hasta dónde conocemos todos los primos.
Pongo "actualmente conocido públicamente" porque existe la posibilidad de que alguna agencia gubernamental tenga una lista más larga por razones de criptografía o algo así.
La forma más eficiente conocida (por favor, corregidme si me equivoco) de generar una lista de primos consecutivos a partir de $2$ a $n$ es la Criba de Eratóstenes, que en una implementación optimizada (al menos contando con lo que está escrito en Wikipedia ) requiere $O(n)$ tiempo y algo así como $O(n^{1/2+\epsilon})$ memoria. Teniendo en cuenta las capacidades informáticas actuales, supongo que su primo está en algún lugar entre $2^{50}$ y $2^{60}$ .
Editar para aclarar: Pedir una respuesta exacta no tiene sentido, porque dado un primo de ese tamaño, es bastante rápido calcular el siguiente.
Edición 2 para responder a su pregunta con otra pregunta. ¿Qué quiere decir con "conocido"? ¿Quieres que todos estén escritos en una lista física? Según el teorema de los números primos, hay unos $\frac n {\log n}$ primos hasta $n$ por lo que se necesitaría un papel bastante grande (o un disco duro) para anotar los primos hasta $2^{60}$ :)
Qué bien, no lo conocía. Pero no cambia mucho mi suposición. (Y no puedes hacerlo mejor que $O(\frac {n}{\log n})$ al menos, por PNT).
En el caso de primos muy grandes, creo que se utilizan enfoques probabilísticos para verificar la primacía. Así que creo que es posible que podamos conseguir más rápido el $ \mathcal{O}\left(\frac{n}{\log n}\right) $ a expensas de la precisión, que podemos rectificar verificando posteriormente el primado con otro ordenador.
Mira este sitio . Si se desplaza lo suficiente, supongo que llegará al mayor primo conocido sin que haya primos menores que él. Sin embargo, su afirmación podría ser errónea, así que no me lo tengas en cuenta si en realidad no tienen todos los primos descubiertos hasta ahora.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
math.stackexchange.com/tags/prime-numbers/info
0 votos
Una lista de este tipo sería totalmente inútil para las criptomonedas.
0 votos
@CodesInChaos ¿Por qué?
0 votos
@AlexanderGruber No se me ocurre ninguna utilidad. Si quieres usarlos para romper RSA, eso no tiene remedio. Incluso el RSA512 fácil de romper tiene primos de 256 bits, de los cuales hay lejos más de lo que se puede calcular o almacenar. Hay algoritmos que utilizan primos más pequeños, por ejemplo Poly1305 utiliza un primo de 130 bits. Pero ese primo no es secreto, y fue elegido por ser el mayor primo menor que 2^130.
0 votos
¿No tiene valor para la investigación en criptografía el estudio de familias de números primos específicos?
0 votos
¿Cómo quiere definir "públicamente conocido"? ¿Requiere que el número esté escrito de alguna manera (electrónica) disponible al público?
0 votos
@MarcvanLeeuwen Eso es lo que tenía en mente, pero como a continuación, esa pregunta podría no ser demasiado útil.
0 votos
La razón por la que esa lista sería inútil es que no aportaría ningún beneficio. El problema de factorizar un número grande no es que sea difícil encontrar primos como candidatos, sino que hay muchos y hay que probarlos todos, y no se obtiene ninguna información útil del fracaso de un primo como factor para encontrar los factores reales. Incluso a 10^18 la distancia entre primos es inferior a 1500, así que incluso si sólo conocieras los primos seguirías teniendo más de 10^14 de ellos para probar.