Generación de primos

En la teoría computacional de números , una variedad de algoritmos hacen posible generar números primos de manera eficiente. Estos se utilizan en varias aplicaciones, por ejemplo , hash , criptografía de clave pública y búsqueda de factores primos en grandes cantidades.

Para números relativamente pequeños, es posible aplicar la división de prueba a cada número impar sucesivo . Los tamices de cebado son casi siempre más rápidos. El tamizado primario es la forma más rápida conocida de enumerar de manera determinista los números primos. Hay algunas fórmulas conocidas que pueden calcular el siguiente primo, pero no existe una forma conocida de expresar el siguiente primo en términos de los primos anteriores. Además, no existe una manipulación general conocida y / o extensión efectiva de alguna expresión matemática (incluso las que incluyen los números primos posteriores) que calcula de manera determinista el siguiente primo.

Tamices de cebado

Un tamiz de números primos o un tamiz de números primos es un tipo rápido de algoritmo para encontrar números primos. Hay muchos tamices de primera calidad. El tamiz simple de Eratóstenes (250s AC), el tamiz de Sundaram (1934), el tamiz aún más rápido pero más complicado de Atkin ^[1] , y varios tamices de rueda ^[2] son los más comunes.

Un tamiz principal funciona creando una lista de todos los números enteros hasta un límite deseado y eliminando progresivamente los números compuestos (que genera directamente) hasta que solo quedan los números primos. Ésta es la forma más eficaz de obtener una amplia gama de números primos; sin embargo, para encontrar primos individuales, las pruebas directas de primalidad son más eficientes ^{[ cita requerida ]} . Además, en base a los formalismos de tamices, se construyen algunas secuencias enteras (secuencia A240673 en la OEIS ) que también podrían usarse para generar primos en ciertos intervalos.

Grandes números primos

Para los primos grandes utilizados en criptografía, los primos probables se pueden generar usando variantes de la prueba de primalidad de Pocklington o primos probables usando pruebas de primalidad probabilísticas estándar como la prueba de primalidad de Baillie-PSW o la prueba de primaria de Miller-Rabin . Tanto las pruebas de primalidad probables como probables utilizan exponenciación modular, un cálculo comparativamente caro. Para reducir el costo computacional, los números enteros se verifican primero en busca de divisores primos pequeños usando tamices similares al Tamiz de Eratóstenes o la división de prueba .

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

Complejidad

El tamiz de Eratóstenes se considera generalmente el tamiz más fácil de implementar, pero no es el más rápido en el sentido del número de operaciones para un rango dado para rangos de tamizado grandes. En su implementación estándar habitual (que puede incluir factorización de rueda básica para primos pequeños), puede encontrar todos los primos hasta N en el tiempo , mientras que las implementaciones básicas del tamiz de Atkin y los tamices de rueda corren en tiempo lineal . Las versiones especiales del tamiz de Eratóstenes que utilizan los principios del tamiz de rueda pueden tener este mismo ${\displaystyle O(N\log \log N)}$${\displaystyle O(N)}$${\displaystyle O(N)}$complejidad del tiempo. Una versión especial del Tamiz de Atkin y algunas versiones especiales de tamices de rueda que pueden incluir el tamizado utilizando los métodos del Tamiz de Eratóstenes pueden funcionar en una complejidad de tiempo sublineal de . Tenga en cuenta que el hecho de que un algoritmo tenga una complejidad de tiempo asintótica disminuida no significa que una implementación práctica se ejecute más rápido que un algoritmo con una complejidad de tiempo asintótica mayor: si para lograr esa complejidad de tiempo asintótica menor, las operaciones individuales tienen un factor constante de complejidad de tiempo aumentada que puede ser muchas veces mayor que para el algoritmo más simple, puede que nunca sea posible dentro de los rangos de tamizado prácticos por la ventaja del número reducido de operaciones para rangos razonablemente grandes para compensar este costo adicional en tiempo por operación.${\displaystyle O(N/\log \log N)}$

Algunos algoritmos de tamizado, como el Tamiz de Eratóstenes con grandes cantidades de factorización de rueda, toman mucho menos tiempo para rangos más pequeños de lo que indicaría su complejidad de tiempo asintótico porque 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, el tamiz de Eratóstenes con una combinación de factorización de la rueda y selección previa utilizando números primos pequeños de hasta 19 utiliza un tiempo de aproximadamente un factor de dos menos que el predicho para el rango total para un rango de 10 ¹⁹ , cuyo rango total toma cientos de años-núcleo para tamizar para obtener los mejores algoritmos de tamizado.

Los tamices simples e ingenuos de "una matriz de tamizado grande" de cualquiera de estos tipos de tamices ocupan un espacio de memoria de aproximadamente , lo que significa que 1) están muy limitados en los rangos de tamizado que pueden manejar con respecto a la cantidad de RAM (memoria) disponible y 2) que por lo general son bastante lentos, ya que la velocidad de acceso a la memoria generalmente se convierte en el cuello de botella de la velocidad más que la velocidad computacional una vez que el tamaño de la matriz crece más allá del tamaño de las memorias caché de la CPU. Los tamices segmentados de página normalmente implementados de Eratóstenes y Atkin ocupan espacio${\displaystyle O(N)}$${\displaystyle O(N/\log N)}$además de pequeños búferes de segmentos de tamiz que normalmente tienen el tamaño adecuado para caber en la memoria caché de la CPU; los tamices de rueda segmentados de páginas, incluidas las variaciones especiales del Tamiz de Eratóstenes, suelen ocupar mucho más espacio que este por un factor significativo para almacenar las representaciones de ruedas requeridas; La variación de Pritchard del tamiz de complejidad de tiempo lineal de Eratóstenes / tamiz de rueda ocupa espacio. La mejor versión especial de complejidad temporal del Tamiz de Atkin ocupa espacio . Sorenson ^[3] muestra una mejora en el tamiz de rueda que ocupa incluso menos espacio para cualquier${\displaystyle O(N^{1/2}\log \log N/\log N)}$${\displaystyle N^{1/2+o(1)}}$${\displaystyle O(N/((\log N)^{L}\log \log N))}$${\displaystyle L>1}$. Sin embargo, la siguiente es una observación general: cuanto más se reduce la cantidad de memoria, mayor es el aumento del factor constante en el costo en tiempo por operación, aunque la complejidad del tiempo asintótico puede permanecer igual, lo que significa que las versiones con reducción de memoria pueden ejecutar muchas veces más lento que las versiones sin reducción de memoria en un factor bastante grande.

Ver también

• Fórmula para primos

Referencias

1. Atkin, A .; Bernstein, DJ (2004). "Cebar tamices utilizando formas cuadráticas binarias" (PDF) . Matemáticas de la Computación . 73 (246): 1023–1030. Código Bibliográfico : 2004MaCom..73.1023A . doi : 10.1090 / S0025-5718-03-01501-1 .
2. Pritchard, Paul (1994). Tamices de números primos incrementales mejorados . Simposio de teoría algorítmica de números. págs. 280–288. CiteSeerX 10.1.1.52.835 . 
3. Sorenson, JP (1998). "Intercambio de tiempo por espacio en tamices de números primos". Teoría algorítmica de números . Apuntes de conferencias en Ciencias de la Computación . 1423 . págs. 179–195. CiteSeerX 10.1.1.43.9487 . doi : 10.1007 / BFb0054861 . ISBN  978-3-540-64657-0.