Criptografía (CCLX): Test de primalidad de Miller-Rabin en python

Continúo poniendo scripts de programación en python para automatizar tareas que tengan relación con la criptografía.

En este post incluyo un script en python que implementa el Test de primalidad de Miller-Rabin, posiblemente el algoritmo probabilista más utilizado para conocer con un alto grado de certeza si un número es primo o compuesto.

La cuestión de conocer si un número dado es primo o compuesto se conoce como el problema de la primalidad.

Ya expliqué en este post la importancia que tiene esta cuestión en la criptografía moderna (por ejemplo, a la hora de generar el par de claves, pública y privada, para un usuario en el criptosistema RSA de cifrado asimétrico) y que no es un asunto trivial cuando se trata de números muy grandes, ya que no se pueden utilizar algoritmos deterministas para saber con seguridad matemática al 100% si un número dado es o no primo, por lo que se recurre a algoritmos probabilistas muy simples y eficiente (Test de primalidad) que nos pueden decir con un elevado nivel de confianza si un número es primo o compuesto, como es el caso del Test de primalidad de Miller-Rabin.

Además, en la citada entrada puse el pseudocódigo para implementarlo:

- Script python para implementar el test de primalidad de Miller-Rabin:

El script es el siguiente:

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

# TEST DE PRIMALIDAD DE MILLER-RABIN:
#
# Test para conocer si un determinado número es primo con un cierto nivel de confianza.
# El valor de k (número de rondas a ejecutar) determina el nivel de confianza del test,
# es decir, si tras el test el número en cuestión es declarado primo, la confianza en que
# realmente lo sea es mayor cuanto mayor sea el valor de k con el que se ha ejecutado el
# test.
#
# http://mikelgarcialarragan.blogspot.com/

from random import randint
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 main():
# MENÚ:
# Se presenta el menú para que se seleccione una opción.
    salir = False
    while not salir:
        print ("")
        print ("*** MENÚ *****************************************")
        print ("1. Test de primalidad de Miller-Rabin.")
        print ("2. Salir.")
        print ("")
        opcion = input("Por favor, seleccione una opción: ")
        if opcion == "1":
            print ("")
            print ("--- TEST DE PRIMALIDAD DE MILLER-RABIN:")
            # Se introducen el número natural mayor que 1 del que se desea conocer si es primo con un cierto
            # nivel de confianza y el número de rondas a ejecutar el test.
            n = k = "*"
            while not n.isnumeric() or int(n) <= 1:
                n = input('Introduzca el número natural mayor que 1 del que desea conocer si es primo: ')
                if n.isnumeric() and int(n) >= 2:
                    if int(n) >= 2:
                        if int(n) ==2:
                            inicio_test = time()
                            print("[+] 2 es el único número par primo.")
                            print('[+] Tiempo de ejecucion del test en segundos:', time() - inicio_test)
                        elif int(n) % 2 == 0:
                            inicio_test = time()
                            print("[+] El número", n, "no es primo. El único número par primo es el 2.")
                            print('[+] Tiempo de ejecucion del test en segundos:', time() - inicio_test)
                        else:
                            while not k.isnumeric() or int(k) <= 0:
                                k = input('Introduzca el número de rondas a ejecutar el test: ')
                                if k.isnumeric() and int(k) >= 1:
                                    inicio_test = time()
                                    if test_miller_rabin(int(n),int(k)):
                                        print("[+] El número", n, "probablemente es primo.")
                                    else:
                                        print("[+] El número", n, "es compuesto.")
                                    print('[+] Tiempo de ejecucion del test en segundos:', time() - inicio_test)
                                else:
                                    print ("*** ERROR: Número de rondas a ejecutar el test incorrecto.")
                    else:
                        print ("*** ERROR: El número del que desea conocer si es primo debe ser un número natural mayor que 1.")
                else:
                    print ("*** ERROR: Número incorrecto. Por favor, introduzca el número natural mayor que 1 del que desea conocer si es primo.")
        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: