Generación de Primos

Renzo Damian Gomez
Nov 2 · 3 min read

Los números primos son esenciales en la criptografía ya que son ellos los que se encargan de dar seguridad a los datos encriptados, su generación rápida y eficaz permite encriptar datos al instante logrando ser parte de varias aplicaciones del día a día (whatsapp, facebook, criptomonedas,twitter..).

Pero, cómo se generan números primos de forma rápida?

Fermat little Theorem

Fermat demostró que p es primo si para todo a dentro de 1<a<p se cumple que a^(p-1) mod p = 1.

En python se escribiría así:

Sin embargo, existen 2 problemas:

  • Existen los llamados Carmichael numbers que son números que pasan el test de Fermat pero no son primos.
  • Si queremos comprobar que un número es primo, el programa tiene que probar todas las a dentro del espectro 1<a<p-1 y si el número p tiene 15 cifras y es primo el programa tiene que realizar 10¹⁵ operaciones. Que ,incluso para una computadora potente, tomaría unos 20 minutos.
Una eternidad……

Si queremos generar números primos grandes Fermat tomaría demasiado tiempo.

Test de probabilidad Miller-Rabin

Miller y Rabin descubrieron la siguiente teoría basada en el teorema de Fermat que simplifica las operaciones por realizar pero la teoría es más compleja.

  1. Generamos un número n que sea impar.
  2. Hallamos s y r tal que n-1 = 2^s * r
  3. Escogemos aleatoriamente un a entre <1,n]
  4. n es un primo potencial si se cumple a^r mod n =1 o a^((2^j) * r) mod n = n-1 para algun j entre 0<j<s
  5. Si no se cumple ningunas de las dos condiciones entonces n es compuesto

Si pasa el test entonces hay una posibilidad de 1/4 de que sea compuesto, por lo tanto, para asegurar el mínimo de probabilidad de que resulte compuesto, realizaremos el test 128 veces. Entonces la probabilidad que sea compuesto se reduce a 0,25¹²⁸.

Por esta razón es el algoritmo más usado en criptografía

Ejemplo para hallar r y s:

n = 29
r =29–1
r= 28/2=14 , s=1
r= 14/2 = 7 , s=2 #7 no es divisible entre 2 entonces:
r= 7, s = 2
n-1 = 2^s * r
29–1 = 2²*7

Ahora a programarlo:

Con este algoritmo el número de iteraciones en el peor de los casos se reduce a s-1 y es mucho más rápido.

Para generar nuestro número primo de 30 cifras o más, simplemente generamos un número aleatorio impar y lo validamos con el algoritmo, si resulta que el número es compuesto, se genera otro número y se repite el proceso hasta que el número generado sea primo.

Probando números hasta encontrar uno primo

Y así es cómo podemos generar números primos de 40, 50 o 60 cifras en un instante.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade