Clases de primos

Primos Seguros

Son primos impares representados como (ε₁, … , ε_k), donde:

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

de esta forma tendríamos (q es otro primo): p = 2q₁ + ε₁ , p₁ = 2q₂ + ε₂ , … , p_k-1 = 2q_k + ε_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,

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 ( a^n-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 = 2i_n + 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

 

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 ♦