Criptografía (CCLXI): Generación de un número primo aleatorio en python

Muy recientemente he puesto una entrada sobre un algoritmo probabilista para conocer, con un elevado nivel de confianza, si un número dado es primo o compuesto.

En concreto, el script en python que puse en dicho post implementa el Test de primalidad de Miller-Rabin, que suele utilizarse para generar números primos aleatorios muy grandes.

En este post pongo un script en python para la generación de un número primo aleatorio muy grande (tamaño igual o mayor que 1.024 bits). 

A efectos prácticos, se suele utilizar un algoritmo como el siguiente:

Al ejecutar el script se pedirá que se seleccione un tamaño mínimo de 1.024 bits para el número impar 'p' a partir del cual se generará el número primo aleatorio, ya que éste suele ser actualmente el tamaño de los dos números primos ('p' y 'q') con cuyo producto se calcula el módulo ('n'), del orden de 2.048 bits, en el criptosistema RSA de cifrado asimétrico, y, por tanto, que sirven como base para generar las claves, pública y privada, de cada usuario.

Asimismo, el script solicitará que se indique un número de rondas igual o superior a 5 para el número de veces que se ejecutará el Test de primalidad de Miller-Rabin para cada número candidato a ser el primo generado, con objeto de obtener un resultado que declare con un elevado nivel de confianza que el número generado es probablemente primo.

- Script python para implementar la generación de un número primo aleatorio muy grande:

El script es el siguiente:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# GENERACIÓN DE UN NÚMERO PRIMO ALEATORIO:
#
# Generación de un número primo aleatorio a partir de un número de b bits.
#
# http://mikelgarcialarragan.blogspot.com/

from sympy import primerange, prime 
from random import randint, getrandbits
from time import time

def test_miller_rabin(n,k):
# n = número natural mayor que 1 e impar del que queremos conocer si es primo.
# k = número de veces o rondas a ejecutar el test.
# t = indicador de que n es primo con un cierto nivel de confianza (0: primo; 1: compuesto).
# s = número de veces que 2 divide a n - 1.
    t = 0
    s = 0
    r = n - 1

    while r%2 == 0:
        s+=1
        r = r//2

    i=0 
    while i in range(0, k) and t != 1:
        a = randint(2, n - 1)
        j = 0
        y = pow(a, r, n)
        if y != 1 and y != n - 1:
            j = 1
            while y != n - 1 and t != 1 and j <= s - 1:
                y = pow(y, 2, n)
                if y == 1:
                    t = 1
                else:
                    j = j + 1
            if y != n -1:
                t = 1
        i = i + 1

    if t == 0:
        return True
    else:
        return False

def generar_primo_aleatorio(b,k):
# b = número de bits que tendrá como mínimo el número primo aleatorio.
# k = número de veces o rondas a ejecutar el test de primalidad.
# Se genera un número aleatorio impar (p) de b bits.
    p = getrandbits(int(b))
    if p%2 == 0:
        p+=1

# Se crea una lista con los primeros 2048 números primos, para descartar rápidamente aquellos
# candidatos no primos, es decir, aquellos que son divisibles por alguno de los números primos
# integrantes de esta lista.
    primeros_2048_primos = list(primerange(prime(2048 + 1)))

# Se realizan las comprobaciones tendentes a verificar si el candidato es primo con un cierto
# nivel de confianza.
    puede_ser_primo = False
    while not puede_ser_primo:
        puede_ser_primo = True
        for primo in primeros_2048_primos:
            if p%primo == 0:
                puede_ser_primo = False
                break
        # Si el candidato supera la primera criba, es decir no es divisible entre ninguno de los primeros
        # 2048 números primos, entonces se le somete al test de primalidad de Miller-Rabin.
        if puede_ser_primo:
            if not test_miller_rabin(p,int(k)):
                puede_ser_primo = False
        # Si el candidato no supera la primera criba, es decir es divisible entre alguno de los primeros
        # 2048 números primos o no supera el test de primalidad de Miller-Rabin, entonces se incrementa
        # al candidato en dos unidades y se vuelve a comprobar si el nuevo candidato puede ser primo.
        if not puede_ser_primo:
                p+=2

    return p

def main():
# MENÚ:
# Se presenta el menú para que se seleccione una opción.
    salir = False
    while not salir:
        print ("")
        print ("*** MENÚ *****************************************")
        print ("1. Generar número primo aleatorio.")
        print ("2. Salir.")
        print ("")
        opcion = input("Por favor, seleccione una opción: ")
        if opcion == "1":
            print ("")
            print ("--- GENERACIÓN DE UN NÚMERO PRIMO ALEATORIO:")
            # Se introducen el tamaño mínimo, número de bits, que tendrá el número primo aleatorio a generar y el número de rondas a ejecutar el test de primalidad
            # para conocer si el número aleatorio impar candidato es primo, o, en su defecto, si lo son los sucesivos números impares de los que se tenga que realizar esta
            # comprobación.
            b = k = "*"
            while not b.isnumeric() or int(b) < 1024:
                b = input('Introduzca el número de bits, sin punto decimal y mayor o igual que 1024, que tendrá como mínimo el nº primo aleatorio a generar: ')
                if b.isnumeric() and int(b) >= 1024: 
                    while not k.isnumeric() or int(k) <= 4:
                        k = input('Introduzca el número, mayor o igual a 5, de rondas a ejecutar el test de primalidad para comprobar que el número a generar es aleatorio: ')
                        if k.isnumeric() and int(k) >= 5:
                            inicio_generacion = time()
                            print("[+] Generando número primo aleatorio...")
                            p = generar_primo_aleatorio(b,k)
                            print("[+] Número primo aleatorio generado:", p)
                            print('[+] Tiempo de ejecucion de la generación del número primo aleatorio:', time() - inicio_generacion)
                        else:
                            print ("*** ERROR: Número de rondas a ejecutar el test de primalidad incorrecto. Debe ser un número natural mayor o igual que 5.")
                else:
                    print ("*** ERROR: Número de bits incorrecto. Debe ser un número natural, sin punto decimal, mayor o igual que 1024.")
        elif opcion == "2":
            print ("*** FIN ******************************************")
            salir = True
        else:
            print ("*** ERROR: Opción no válida.")
	
if __name__ == '__main__':
    main()

Lo ejecuto:

Quizás también te interese: