Esta es una traducción automática y el texto original está en inglés. Leer el original
Los primos se rarifican a un ritmo que se puede nombrar
Cerca de un número de 1024 bits, uno de cada 355 números impares es primo. No es una probabilidad pequeña, y es la única razón por la que la criptografía de clave pública es posible.
Hay 25 primos por debajo de 100, 168 por debajo de 1000 y 78.498 por debajo de un millón. Los recuentos disminuyen, pero nunca se detienen, y el ritmo al que se rarifican es uno de los hechos más útiles de las matemáticas.
Uno de cada ln n
Cerca de un número n, aproximadamente uno de cada ln n números es primo. Por debajo de 100, eso predice 100 / ln 100 = 21,7 primos, y Prime Sieve muestra exactamente eso junto al recuento real de 25, además del error del 13,1%.
La estimación es imprecisa aquí y mejora. En un millón, N / ln N da 72.382 frente a los 78.498 reales, un error del 7,8%. El error relativo se reduce a medida que N crece, lo cual es el contenido real del teorema de los números primos.
La mejor estimación que parece peor
La herramienta muestra una segunda aproximación, Li(N), la integral logarítmica. En N = 100 da 29,1 y es peor que la imprecisa: un error del 16,3% frente al 13,1%.
Cualquiera que lea solo esa fila concluiría que la fórmula más elaborada no vale la pena. Al cambiar N, el orden se invierte y nunca vuelve a cambiar:
- N = 100: N/lnN se desvía un 13,1%, Li se desvía un 16,3%
- N = 1000: N/lnN se desvía un 13,8%, Li se desvía un 5,1%
- N = 10⁶: N/lnN se desvía un 7,8%, Li se desvía un 0,16%
Li no es tanto un refinamiento de N / ln N como su versión genuina. La fórmula imprecisa aplica la densidad en n a todo el intervalo de 0 a n, cuando la densidad cerca de 2 es muy diferente de la densidad cerca de un millón. Li integra 1/ln t a lo largo del intervalo en lugar de asumirla constante, y la recompensa es un error de una parte en seiscientas allí donde el atajo aún se equivoca por un 8%.
Una sola evaluación de una aproximación no dice nada sobre si es buena. Es necesario conocer su comportamiento a medida que crece la entrada.
Por qué nunca se agotan
Porque 1/ln n disminuye despacio. Su suma diverge, por lo que los primos son escasos, pero no lo bastante escasos como para ser finitos.
La demostración de Euclides es más directa y antigua. Tómese cualquier lista finita de primos, multiplíquense entre sí y súmese uno. El resultado deja un resto de 1 al dividirse por cualquier primo de la lista, por lo que sus factores primos están todos ausentes de la lista. Ninguna lista finita puede estar completa.
Las otras dos lecturas de la herramienta señalan cuánto queda aún por resolver. Cuenta 8 pares de primos gemelos por debajo de 100 y señala que la mayor separación es 8. Si los pares de primos gemelos continúan infinitamente no está demostrado, como tampoco lo está la conjetura de que siempre existe un primo entre cuadrados consecutivos.
El número que determina el tamaño de una clave
Generar una clave RSA requiere encontrar primos grandes, y el método consiste en elegir un número impar aleatorio del tamaño adecuado y probarlo.
El tiempo que lleva es exactamente la cuestión de la densidad. Un número de 1024 bits está cerca de 2¹⁰²⁴, y ln(2¹⁰²⁴) = 1024 × ln 2 = 710. Por tanto, aproximadamente uno de cada 710 números cercanos a ese valor es primo y, dado que solo se prueban candidatos impares, uno de cada 355.
Trescientos cincuenta y cinco ensayos, cada uno de ellos una prueba de primalidad probabilística rápida. Por eso la generación de claves requiere solo un instante en lugar de una era geológica, y todo el cálculo proviene de un logaritmo. Si se aumenta el exponente, el coste crece de forma lineal con la longitud en bits, motivo por el cual las claves de 2048 y 4096 bits siguen siendo prácticas.
Si los primos se hubieran rarificado aunque fuera un poco más rápido, digamos como 1/n, la búsqueda habría sido inviable y la internet se habría construido sobre otra base.
Nadie demuestra los primos que utiliza
Un detalle hace que los 355 ensayos sean económicos: la prueba no establece la primalidad.
Miller-Rabin elige un testigo aleatorio y plantea una pregunta a la que todo número primo responde de una misma manera. Un número compuesto puede responder como un primo, pero como máximo un cuarto de los posibles testigos se lo permitirá, de modo que cada ronda independiente reduce la probabilidad de engaño al menos entre cuatro. Cuarenta rondas dejan el peor caso por debajo de 4⁻⁴⁰, lo que equivale a unos 10⁻²⁴.
Esto se encuentra muy por debajo de la probabilidad de un error de memoria no detectado en el ordenador que realiza los cálculos. Las claves que protegen el tráfico mundial se basan en números que son casi con toda certeza primos, y la duda residual es menor que la del propio hardware.