Número primo fuerte

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]

  1. p es grande.
  2. p − 1 tiene factores primos grandes. Es decir, p = a1q1 + 1 para algún entero a1 y un primo grande q1.
  3. q1 − 1 tiene factores primos grandes. Es decir, q1 = a2q2 + 1para algún entero a2 y un primo grande q2.
  4. 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:

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 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

  1. 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
  2. sucesión A051634 en OEIS

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Número primo — Un número primo es un número natural mayor que 1, que tiene únicamente dos divisores distintos: él mismo y el 1. Se contraponen así a los números compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número …   Wikipedia Español

  • Número primo de Mersenne — Se dice que un número M es un número de Mersenne si es una unidad menor que una potencia de 2. Mn = 2n − 1. Un número primo de Mersenne es un número de Mersenne que es primo, es decir, Mn = 2n − 1, con n primo (no es una condición suficiente que… …   Wikipedia Español

  • Número primo equilibrado — En Matemáticas un primo equilibrado es un número primo tal que es igual a 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: Los… …   Wikipedia Español

  • José Antonio Primo de Rivera — Para otros usos de este término, véase Primo de Rivera. «José Antonio» redirige aquí. Para otras acepciones, véase José Antonio (desambiguación). José Antonio Primo de Rivera …   Wikipedia Español

  • Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español

  • Hipótesis H de Schinzel — En matemáticas, la hipótesis H de Schinzel es una generalización muy amplia de conjeturas tales como la de los números primos gemelos. La hipótesis aspira a definir el ámbito más amplio que puede tener una conjetura de la naturaleza de que una… …   Wikipedia Español

  • Conjetura de Goldbach — En teoría de números, la conjetura de Goldbach es uno de los problemas abiertos más antiguos en matemáticas. A veces se le califica del problema más difícil en la historia de esta ciencia. Su enunciado es el siguiente: Todo número par mayor que 2 …   Wikipedia Español

  • Conjetura de Cramér — En teoría de números, la conjetura de Cramér, formulada por el matemático sueco Harald Cramér en 1936,[1] dice que donde pn denota el n ésimo número primo y log denota el logaritmo natural. Esta conjetura aún no ha sido demostrada ni refutada, y… …   Wikipedia Español

  • Wikipedia:Artículos buenos —   Artículos buenos   ¿Qué es un artículo bueno?   …   Wikipedia Español

  • Wikipedia:Artículos peculiares — Atajos WP:PECULWP:PECUL WP:RAROWP:RARO …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”