Hispanopedia WikiEn matemáticas , un primo fuerte es un número primo con ciertas propiedades especiales. Las definiciones de primos fuertes difieren en criptografía y teoría de números .
Definición en teoría de números
En teoría de números , un primo fuerte es un número primo que es mayor que la media aritmética del primo más cercano por encima y por debajo (es decir, está más cerca del primo siguiente que del anterior). O, dicho algebraicamente, escribiendo la secuencia de números primos como (p₁, p₂, p₃, ...) = (2, 3, 5, ...), pₙ es un primo fuerte si pₙ > pₙ - 1 + pₙ + 1 / 2. Por ejemplo , 17 es el séptimo primo : el sexto y el octavo primos , 13 y 19 , suman 32 , y la mitad es 16; 17 es mayor que 16, por lo que 17 es un primo fuerte.
Los primeros números primos fuertes son
- 11 , 17 , 29 , 37 , 41 , 59 , 67 , 71 , 79 , 97 , 101 , 107 , 127 , 137 , 149 , 163 , 179 , 191 , 197 , 223 , 227 , 239 , 251 , 269 , 277 , 281 , 307 , 311, 331, 347, 367, 379, 397, 419, 431, 439, 457, 461, 479, 487, 499 (secuencia A051634 en el OEIS ) .
En un par de primos gemelos ( p , p + 2) con p > 5, p siempre es un primo fuerte, ya que 3 debe dividir a p − 2, que no puede ser primo.
Definición en criptografía
En criptografía , se dice que un número primo p es "fuerte" si se cumplen las siguientes condiciones. [ 1 ]
- p es suficientemente grande como para ser útil en criptografía; normalmente esto requiere que p sea demasiado grande para que los recursos computacionales plausibles permitan a un criptoanalista factorizar productos de p con otros primos fuertes.
- p − 1 tiene factores primos grandes. Es decir, p = a 1 q 1 + 1 para algún entero a 1 y un primo grande q 1 .
- q 1 − 1 tiene factores primos grandes. Es decir, q 1 = a 2 q 2 + 1 para algún entero a 2 y un primo grande q 2 .
- p + 1 tiene factores primos grandes. Es decir, p = a 3 q 3 − 1 para algún entero a 3 y un primo grande q 3 .
Es posible que un número primo sea un primo fuerte tanto en el sentido criptográfico como en el sentido de la teoría de números. A modo de ejemplo, 439351292910452432574786963588089477522344331 es un primo fuerte en el sentido de la teoría de números porque la media aritmética de sus dos primos vecinos es 62 unidades menor. 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 ese tiene el factor primo grande 1683837087591611009), 439351292910452432574786963588089477522344332 tiene el factor primo grande 864608136454559457049 (y a su vez el número uno menos que ese tiene el factor primo grande 105646155480762397). Incluso utilizando algoritmos más avanzados que la división por tanteo , sería difícil factorizar estos números a mano. Para un sistema moderno de álgebra computacional , estos números se pueden factorizar casi instantáneamente. Un número primo criptográficamente seguro debe ser mucho mayor que este ejemplo.
Aplicación de números primos fuertes en criptografía
Sistemas criptográficos basados en factorización
Algunas personas sugieren que, en el proceso de generación de claves en los sistemas criptográficos RSA , el módulo n debería elegirse como el producto de dos primos fuertes. Esto hace que la factorización de n = pq mediante el algoritmo p − 1 de Pollard sea computacionalmente inviable. Por esta razón, el estándar ANSI X9.31 exige primos fuertes para la generación de claves RSA para firmas digitales . Sin embargo, los primos fuertes no protegen contra la factorización del módulo mediante algoritmos más recientes, como la factorización de curvas elípticas de Lenstra y el algoritmo Number Field Sieve . Dado el coste adicional de generar primos fuertes, RSA Security no recomienda actualmente su uso en la generación de claves . Rivest y Silverman también presentan un argumento similar (y más técnico). [ 1 ]
Sistemas criptográficos basados en logaritmos discretos
Stephen Pohlig y Martin Hellman demostraron en 1978 que si todos los factores de p − 1 son menores que log c p , entonces el problema de resolver el logaritmo discreto módulo p pertenece a P. Por lo tanto, para los criptosistemas basados en el logaritmo discreto, como DSA , se requiere que p − 1 tenga al menos un factor primo grande.
Datos diversos
Es probable que un número primo seguro computacionalmente grande sea también un número primo criptográficamente fuerte.
Cabe señalar que el criterio para determinar si un número pseudoprimo es un pseudoprimo fuerte se basa en congruencias con potencias de una base, no en desigualdades con la media aritmética de los números pseudoprimos vecinos.
Cuando un número primo es igual a la media de sus primos vecinos, se le llama primo equilibrado . Cuando es menor, se le llama primo débil (que no debe confundirse con un número débilmente primo ).
Referencias
Enlaces externos
- Guía de criptografía y estándares
- 3.1.4 ¿Qué son los números primos fuertes y son necesarios para el sistema RSA? - Explicación de RSA Lab sobre números primos fuertes y débiles
- Clases de números primos
- Teoría de la criptografía