En matemáticas , un número primo fuerte es un número primo con ciertas propiedades especiales. Las definiciones de números primos fuertes son diferentes en criptografía y teoría de números .
En teoría de números , un número primo fuerte es un número primo que es mayor que la media aritmética del primo más cercano arriba y abajo (en otras palabras, está más cerca del siguiente que del anterior). O para decirlo algebraicamente, escribiendo la secuencia de números primos como ( p 1 , p 2 , p 3 , ...) = (2, 3, 5, ...), p n es un primo fuerte si p n > p n - 1 + p n + 1 / 2. Por ejemplo, 17 es el séptimo primo: los primos sexto y octavo, 13 y 19, suman 32, y la mitad es 16; 17 es mayor que 16, por lo que 17 es un número primo fuerte.
En un par de primos gemelos ( p , p + 2) con p > 5, p es siempre un primo fuerte, ya que 3 debe dividir p - 2, que no puede ser primo.
En criptografía , se dice que un número primo p es "fuerte" si se cumplen las siguientes condiciones. [1]
Es posible que un primo sea un primo fuerte tanto en el sentido criptográfico como en el teórico de números. Por el bien de la ilustración, 439351292910452432574786963588089477522344331 es un número primo fuerte en el sentido teórico de los números porque la media aritmética de sus dos primos vecinos es 62 menos. Sin la ayuda de una computadora, este número sería un primo fuerte en el sentido criptográfico porque 439351292910452432574786963588089477522344330 tiene el factor primo grande 1747822896920092227343 (y a su vez el número uno menos que tiene el factor primo grande 1683837087591611009443 864608136454559457049 (y, a su vez, el número uno menos que tiene el factor primo grande 105646155480762397). Incluso usando algoritmos más avanzados quedivisión de prueba , estos números serían difíciles de factorizar a mano. Para un sistema de álgebra computacional moderno , estos números se pueden factorizar casi instantáneamente. Un primo criptográficamente fuerte tiene que ser mucho más grande que este ejemplo.
Algunas personas sugieren que en el proceso de generación de claves en los criptosistemas RSA , el módulo n debe elegirse como el producto de dos números primos fuertes. Esto hace que la factorización de n = pq utilizando el algoritmo p - 1 de Pollard sea computacionalmente inviable. Por esta razón, el estándar ANSI X9.31 requiere números primos fuertes para su uso en la generación de claves RSA para firmas digitales . Sin embargo, los números primos fuertes no protegen contra la factorización del módulo utilizando algoritmos más nuevos como la factorización de la curva elíptica Lenstra y el tamiz de campo numérico.algoritmo. Dado el costo adicional de generar números primos fuertes, RSA Security actualmente no recomienda su uso en la generación de claves . Rivest y Silverman también dan un argumento similar (y más técnico). [1]