- Número primo fuerte
-
En matemáticas, un número primo fuerte es un número primo con ciertas propiedades. La definición de primo fuerte es diferente en criptografía y en la teoría de números.
Contenido
Definición en criptografía
En criptografía un número primo es fuerte si satisface las siguientes condiciones:[1]
- p es grande.
- p − 1 tiene factores primos grandes. Es decir, p = a1q1 + 1 para algún entero a1 y un primo grande q1.
- q1 − 1 tiene factores primos grandes. Es decir, q1 = a2q2 + 1para algún entero a2 y un primo grande q2.
- p + 1 tiene factores primos grandes. Es decir, p = a3q3 − 1 para algún entero a3 y un primo grande q3.
En algún caso, además de las condiciones anteriores, se impone que a1 = 2 o a2 = 2, etc.
Definición en la teoría de números
En la teoría de números un número primo fuerte es un número primo tal que es mayor que la media aritmética de sus primos predecesor y sucesor. De otro modo, si para un primo dado pn, donde n es el índice en el conjunto ordenado de los primos naturales:
Por ejemplo, 17 es el séptimo primo; el sexto y el octavo, 13 y 19, sumados dan 32 cuya mitad es 16 que es menor que 17, luego 17 es un primo fuerte.
En un par de primos gemelos (p, p + 2) con p > 5, p es siempre un primo fuerte ya que 3 divide a p − 2 con lo que no podrá ser primo.
Un número primo puede ser fuerte en los dos sentidos considerados.
Por ejemplo, el 439.351.292.910.452.432.574.786.963.588.089.477.522.344.331 es un primo fuerte en sentido de la teoría de números puesto que es 62 unidades mayor que la media aritmética de sus primos vecinos. Sin la ayuda de un ordenador también lo sería en sentido criptográfico puesto que 439.351.292.910.452.432.574.786.963.588.089.477.522.344.330 tiene el gran factor primo 1.747.822.896.920.092.227.343 (y, además, restando una unidad a este último obtenemos otro número con el gran factor primo 1683837087591611009), 439.351.292.910.452.432.574.786.963.588.089.477.522.344.332 tiene el gran factor primo 864.608.136.454.559.457.049 (y, además, restando una unidad a este último obtenemos otro número con el gran factor primo 105.646.155.480.762.397). Sin usar otros métodos que la división a mano no es fácil factorizar estos números. Con un sistema algebraico computacional estos números se factorizan casi instantáneamente así que un primo criptográficamente fuerte debería ser mucho mayor que el del ejemplo.
Números fuertes menores a 500
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.[2]
Aplicación de los primos fuertes en criptografía
Criptosistemas basados en la factorización
Se ha sugerido que en la generación de claves de los criptosistemas tipo RSA el módulo n debería escogerse como el producto de dos primos fuertes. Esto haría computacionalmente no factible la factorización de n = pq usando el algoritmo p-1 de Pollard. Por esta razón se requieren los primos fuertes en la norma ANSI X9.31 para la generación de claves RSA de firmas digitales. Sin embargo, los primos fuertes no protegen contra la factorización modular que usan los más recientes algoritmos tales como la factorización Lenstra con curvas elípticas y la criba del cuerpo de números. Dado el coste adicional en la generación de primos fuertes actualmente no se recomienda en la generación de claves. Argumentos similares (y más técnicos) han dado Rivest and Silverman.[1]
Criptosistemas basados en el logaritmo discreto
En 1978 Stephen Pohlig y Martin Hellman demostraron que si todos los factores de p-1 son menores que logcp entonces el problema de hallar el logaritmo discreto módulo p está en P. Por consiguiente, para sistemas basados en el logaritmo discreto tales como el DSA se requiere que p-1 tenga al menos un gran factor primo.
Véase también
Un primo seguro computacionalmente grande es, seguramente, un primo fuerte criptográfico. Nótese que los criterios para determinar si un pseudoprimo es un pseudoprimo fuerte son con congruencias de potencias de la base, no por la desigualdad con la media aritmética de los primos vecinos.
Si un número primo es igual a la media de sus primos vecinos se dice primo equilibrado y si es menor primo débil.
Notas
- ↑ a b Ron Rivest and Robert Silverman, Are 'Strong' Primes Needed for RSA?, Cryptology ePrint Archive: Report 2001/007. http://eprint.iacr.org/2001/007
- ↑ sucesión A051634 en OEIS
Enlaces externos
Categoría:- Sucesiones de números primos
Wikimedia foundation. 2010.
