Generación de números primos

En la teoría computacional de números , diversos algoritmos permiten generar números primos de manera eficiente. Estos se utilizan en diversas aplicaciones, como el hashing , la criptografía de clave pública y la búsqueda de factores primos en grandes conjuntos de datos.

Para números relativamente pequeños, es posible aplicar la división por tanteo a cada número impar sucesivo . El cribado de primos es casi siempre más rápido. El cribado de primos es la forma más rápida conocida de enumerar los primos de manera determinista. Existen algunas fórmulas conocidas que pueden calcular el siguiente primo, pero no hay una forma conocida de expresar el siguiente primo en términos de los primos anteriores. Además, no existe ninguna manipulación general efectiva conocida o extensión de alguna expresión matemática (incluso que incluya primos posteriores) que calcule de forma determinista el siguiente primo.

Un cribado de primos o criba de números primos es un tipo de algoritmo rápido para encontrar primos. Existen muchos cribados de primos. El cribado simple de Eratóstenes (250 a. C.), el cribado de Sundaram (1934), el cribado de Atkin ^{[ 1 ]} (2003), aún más rápido pero más complejo , el cribado de Pritchard (1979) y varios cribados de rueda ^{[ 2 ]} son ​​los más comunes.

El método de cribado de primos funciona creando una lista de todos los enteros hasta un límite deseado y eliminando progresivamente los números compuestos (que genera directamente) hasta que solo quedan primos. Este es el método más eficiente para obtener un amplio rango de primos; sin embargo, para encontrar primos individuales, las pruebas de primalidad directas son más eficientes . Además, basándose en los formalismos del cribado, se construyen algunas secuencias de enteros (secuencia A240673 en la OEIS ) que también podrían utilizarse para generar primos en ciertos intervalos.

Históricamente, algunos de los tamices principales se realizaron total o parcialmente en hardware, incluyendo las plantillas utilizadas por Anton Felkel , Carl Hindenburg y D.  N. Lehmer como ayudas para el cálculo manual; y las máquinas electromecánicas, y una máquina electrónica posterior, conocidas como los tamices de Lehmer por D.  H. Lehmer (en al menos una ocasión con D.  N. Lehmer). ^{[ 3 ] [ 4 ]}

La criptografía requiere el uso de primos muy grandes: por ejemplo, con el sistema criptográfico RSA se recomiendan dos primos de al menos 1024 bits (es decir, al menos ^2¹⁰²³ ) . ^{[ 5 ]} Para generar estos primos, el método principal consiste en generar números aleatorios en un rango objetivo y comprobar su primalidad mediante métodos probabilísticos rápidos: una ronda corta de cribado ( crija de Eratóstenes o división por ensayo ) seguida de la prueba de primalidad de Baillie-PSW o la prueba de primalidad de Miller-Rabin ; ^{[ 6 ]} un primo probable con una probabilidad de ^2¹¹² de ser compuesto se considera suficiente para el caso de 2048 bits. Incluso si se elige un número compuesto, es probable que se descubra rápidamente al provocar fallos en las operaciones, excepto cuando se elige un número de Carmichael en el caso de RSA. ^{[ 7 ]}

Una opción menos común es usar primos demostrables , que pueden generarse a partir de variantes de la prueba de primalidad de Pocklington , ^{[ 8 ]} especialmente el algoritmo de Maurer. Tanto las pruebas de primalidad demostrables como las probables se basan en la exponenciación modular . ^{[ 6 ]}

Además, con RSA, se prefieren los llamados "primos fuertes", donde tanto p-1 como p+1 tienen un factor primo grande, ^{[ 6 ]} ya que se espera que esto ralentice los intentos de factorización utilizando los algoritmos de Polard para p-1 y Williams para p+1. Sin embargo, esta elección tiene poco efecto contra los métodos de factorización de curvas elípticas. ^{[ 9 ]}

Los números enteros de formas especiales, como los primos de Mersenne o los primos de Fermat , pueden comprobarse de forma eficiente para determinar su primalidad si se conoce la factorización prima de p − 1 o p + 1.    

La criba de Eratóstenes se considera generalmente la criba más fácil de implementar, pero no es la más rápida en términos del número de operaciones para un rango dado en rangos de cribado grandes. En su implementación estándar habitual (que puede incluir la factorización básica de la rueda para primos pequeños), puede encontrar todos los primos hasta N en tiempo${\displaystyle O(N\log \log N),}$mientras que las implementaciones básicas del tamiz de Atkin y los tamices de rueda se ejecutan en tiempo lineal.${\displaystyle O(N)}$Las versiones especiales del tamiz de Eratóstenes que utilizan principios de tamiz de rueda pueden tener esta misma linealidad.${\displaystyle O(N)}$complejidad temporal. Una versión especial de la criba de Atkin y algunas versiones especiales de cribas de rueda que pueden incluir el cribado utilizando los métodos de la criba de Eratóstenes pueden ejecutarse con una complejidad temporal sublineal de${\displaystyle O(N/\log \log N)}$Cabe señalar que el hecho de que un algoritmo tenga una complejidad temporal asintótica reducida no significa que una implementación práctica sea más rápida que un algoritmo con una complejidad temporal asintótica mayor: si para lograr esa menor complejidad asintótica las operaciones individuales tienen un factor constante de aumento de la complejidad temporal que puede ser muchas veces mayor que para el algoritmo más simple, es posible que dentro de los rangos de cribado prácticos nunca sea posible que la ventaja de la reducción del número de operaciones para rangos razonablemente grandes compense este coste adicional en tiempo por operación.

Algunos algoritmos de cribado, como la Criba de Eratóstenes con gran cantidad de factorización de rueda, requieren mucho menos tiempo para rangos más pequeños de lo que indicaría su complejidad temporal asintótica, debido a que tienen grandes desplazamientos constantes negativos en su complejidad y, por lo tanto, no alcanzan esa complejidad asintótica hasta mucho más allá de los rangos prácticos. Por ejemplo, la Criba de Eratóstenes con una combinación de factorización de rueda y preselección usando primos pequeños de hasta 19 utiliza un tiempo aproximadamente dos veces menor que el predicho para el rango total de 10 ¹⁹ , cuyo rango total requiere cientos de años de núcleo para ser cribado por el mejor de los algoritmos de cribado.

Los tamices simples e ingenuos de "una gran matriz de tamizado" de cualquiera de estos tipos de tamices ocupan un espacio de memoria de aproximadamente${\displaystyle O(N)}$lo que significa que 1) están muy limitados en los rangos de cribado que pueden manejar a la cantidad de RAM (memoria) disponible y 2) que suelen ser bastante lentos ya que la velocidad de acceso a la memoria normalmente se convierte en el cuello de botella de la velocidad más que la velocidad de cálculo una vez que el tamaño de la matriz crece más allá del tamaño de las cachés de la CPU. Los cribas segmentadas por página normalmente implementadas tanto de Eratóstenes como de Atkin ocupan espacio${\displaystyle O(N/\log N)}$más pequeños búferes de segmento de tamiz que normalmente tienen un tamaño que se ajusta a la caché de la CPU; los tamices de rueda segmentados por página, incluidas variaciones especiales del tamiz de Eratóstenes, suelen ocupar mucho más espacio que esto por un factor significativo para almacenar las representaciones de rueda requeridas; la variación de Pritchard del tamiz de Eratóstenes/tamiz de rueda de complejidad temporal lineal ocupa${\displaystyle O(N^{1/2}\log \log N/\log N)}$espacio. La versión especial de complejidad temporal mejorada de la Criba de Atkin ocupa espacio.${\displaystyle N^{1/2+o(1)}}$. Sorenson ^{[ 10 ]} muestra una mejora en el tamiz de rueda que ocupa aún menos espacio en${\displaystyle O(N/((\log N)^{L}\log \log N))}$para cualquier${\displaystyle L>1}$Sin embargo, cabe hacer la siguiente observación general: cuanto más se reduce la cantidad de memoria, mayor es el aumento constante del factor en el costo en tiempo por operación, aunque la complejidad temporal asintótica pueda permanecer igual, lo que significa que las versiones con memoria reducida pueden ejecutarse muchas veces más lentamente que las versiones sin memoria reducida por un factor bastante grande.

• Fórmula para números primos