Clases de primos

Primos Seguros

Son primos impares representados como (ε1, … , εk), donde:

  • k es > 0, significa n veces seguro y es denominado orden de la signatura
  • 1, … , εk) ∈ { +1, -1}

de esta forma tendríamos (q es otro primo): p = 2q1 + ε1 , p1 = 2q2 + ε2 , … , pk-1 = 2qk + εk

 

Para los primos seguros del tipo 1-seguro existen dos formas { +1, -1}. Los +1 son congruentes con 3 módulo 4, los -1 son congruentes 1 módulo 4.

 

Los primeros son: 5 , 7 , 11 , 23 , 47 , 59 , 83 , 107 , 167 , 179 , 227 , 263 , 347, 359, 383, 467, 479,

Derrick H. LehmerHenry Cabourn Pocklington

La prueba para este tipo de primos es la sugerida en 1.914 por H. Cabourn Pocklington y Derrick H. Lehmer, usan una factorización parcial de N-1 para certificar que N es primo:

 

  1. Tomamos un natural n > 1, tal que 1 < a < n y otro natural q.
  2. Si no existe un primo q > √ n – 1 tal que q|n – 1, entonces n es indeterminado.
  3. Probamos si a n-1 ≡ 1 (mod n), en caso contrario n es compuesto.
  4. Probamos MCD ( an-1/q -1, n) = 1, si es afirmativo n es primo, en caso contrario tomamos otro q y volvemos a comenzar.

 

Primos Fuertes

Los primos fuertes tienen dos definiciones en función de quién los utilice:

  1. En teoría de números es un primo mayor que la media aritmética de sus primos siguiente y anterior. Los primeros son: 11, 17, 29, 37, 41, 59, 67, 71, 79, 97, 101, 107, 127, 137, 149, 163, 179, 191, 197
  2. En criptografía deben cumplir las siguientes condiciones:
    • p debe ser grande > 100 dígitos y además satisfacer:
    • p-1 = 1 mod r
    • p+1 = s -1 mod s
    • r-1 = 1 mod t
    • donde r, s y t son primos aleatorios grandes de un número dado de bits.

En 1.984 John Gordon propone un algoritmo para generar primos fuertes que es algo más eficiente que el de Williams-Schmid. El algoritmo actúa de la siguiente forma:

 

  1. Genera dos primos aleatorios grandes s y t de longitud de bit más o menos igual a la elegida. Pueden ser también probables primos.
  2. Con un número entero i se localiza el primer primo en la secuencia 2it + 1. Este primo es r = 2in + 1
  3. Calcula p0 = 2 (sr-2 mod r) s – 1.
  4. Con un entero j0. Buscamos un primo en la secuencia j0 + 2jrs, ….
  5. Ya tenemos p = j0 + 2jrs

 

Generador de primos fuertes
Generador de primos fuertes

En 1.998, Ronald Rivest y Robert Silverman indicaron que estos primos sólo eran necesarios para soportar la factorización mediante ciertos métodos como el p-1 de Pollard y que el desarrollo de ECM o la criba cuadrática dejaba sin valor este tipo de primos.

 

♦ Descargar ♦