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.

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=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}$ .

En algún caso, además de las condiciones anteriores, se impone que $a_{1}=2$ o $a_{2}=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 $p_{n}$ , donde n es el índice en el conjunto ordenado de los primos naturales:

p_{n}>{{p_{n-1}+p_{n+1}} \over 2}.

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 1 683 837 087 591 611 009), 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 de curva elíptica de Lenstra 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 $log^{c}p$ 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