Criptografía (CCLXXV): Exponenciación modular rápida 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 algoritmo de exponenciación modular rápida.

La exponenciación modular con números muy grandes es ampliamente utilizada en criptografía asimétrica, por lo que se hace necesario utilizar un algoritmo para su cálculo más eficiente que con el método directo, es decir, un algoritmo con menores requerimientos de memoria y más rápido que calcular primero la potencia y después reducir el resultado obtenido al módulo.

El algoritmo más eficiente para ello es el conocido como de exponenciación rápida o exponenciación binaria, que utiliza la expansión binaria del exponente, y cuyo pseudocódigo para su uso en aritmética modular pongo a continuación.

- Script python para implementar el algoritmo de exponenciación modular rápida:

El script es el siguiente:

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

from time import time

# ALGORITMO DE EXPONENCIACIÓN MODULAR RÁPIDA:
#
# Algoritmo utilizado en operaciones de exponenciación modular
# con números muy grandes con objeto de hacerlas de forma
# más eficiente.
#
# http://mikelgarcialarragan.blogspot.com/

def exp_modular_rapida(b, e, m):
    c = 1
    e = bin(e)[2:]

    for i in range(0, len(e)):
        c = pow(c, 2, m)
        if e[i]=="1":
            c = c*b%m

    return c

def main():
# MENÚ:
# Se presenta el menú para que se seleccione una opción.
    salir = False
    while not salir:
        print ("")
        print ("*** MENÚ *****************************************")
        print ("1. Algoritmo de exponenciación modular rápida.")
        print ("2. Salir.")
        print ("")
        opcion = input("Por favor, seleccione una opción: ")
        if opcion == "1":
            print ("")
            print ("--- ALGORITMO DE EXPONENCIACIÓN MODULAR RÁPIDA:")
            # Se introducen la base, el exponente y el módulo.
            base = exponente = modulo = "*"
            while not base.isnumeric() or not exponente.isnumeric() or not modulo.isnumeric():
                base = input('Introduzca la base (b): ')
                exponente = input('Introduzca el exponente (e): ')
                modulo = input('Introduzca el módulo (m): ')
                if base.isnumeric() and exponente.isnumeric() and modulo.isnumeric():
                    inicio_exponenciacion = time()
                    c = exp_modular_rapida(int(base),int(exponente),int(modulo))
                    print("[+] c = b**e mod m =", c)
                    print("[+] Tiempo de ejecucion en segundos:", time() - inicio_exponenciacion)
                else:
                    print ("*** ERROR: La base, el exponente y el módulo deben ser números enteros positivos.")
        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: