Algunos funciones de aritmetica modular en Python

def mcd(n,m):
m_aux = n%m
if( m_aux == 0 ):
return m
elif( m_aux == 1 ):
return 1
else:
return mcd(m,m_aux)


def mcm(n,m):
return (int)( n * m / mcd(n,m) )


def inv_mult(a,n):
if(mcd(a,n)!=1):
print(str(a) + " NO TIENE INVERSO MULTIPLICATIVO EN " + str(n))
else:
for i in range(1,n) :
if( ( a*i-1 )%n == 0 ):
return i


def solv_ecu_lineal(a,c,n):
# Resuleve una ecuacion de la forma aX = c en el campo Zn
# Se puede resolver si a tiene inverso multiplicativo en Zn
# Eso ocurre si mcd(a,n)=1
if( mcd(a,n) == 1 ):
p = inv_mult(a,n)
return (p * c)%n
else:
print("LA ECUACION NO SE PUEDE RESOLVER.")


def get_coprimos(n):
return [i for i in range(1,n) if mcd(i,n)==1]


def phi_euler(n):
return len(get_coprimos(n))

#Potencia implementado de forma iterativa
def pot_e_mod_n(a,e,n):
pot = 1
for i in range(0,e):
pot =  (pot * a) % n
return pot

#Potencia implementado de forma recursiva
def rpot_e_mod_n(a,e,n):
return  1 if (e == 0) else a* rpot_e_mod_n(a,e-1,n)%n


import random
def gen_list_keys(p,q):
phi = (p-1) * (q-1)
# privadas contiene todas las llaves privadas que pueden existir
privadas = list(filter(lambda n: mcd(n,phi)==1,range(2,phi)))
# publicas contiene todas las llaves publicas que pueden existir
publicas = list(map(lambda i: inv_mult(i,phi),privadas))
return (privadas,publicas)

def gen_keys(p,q):
# Este metodo retorna una llave publica, una privada
phi = (p-1) * (q - 1)
(privadas,publicas)= gen_list_keys(p,q)
i = random.randint(2,len(privadas))
key_privada = privadas[i]
key_publica = publicas[i]
return key_publica,key_privada


def rsa(data,pot,n):
return list(map(lambda a: pot_e_mod_n(a,pot,n),data))

# Receptor define p y q, primos
# denifir n = p*q
# encontrar phi = (p-1)*(q-1), o llamar a phi_euler(n)
# encontrar los nros e y d tal que 1< e < phi y mcd(e,phi) = 1 y d*e = 1(mod n)
# el paso anterior se puede hacer por e,d = gen_keys(p,q)
# Receptor guardar d y n
# Receptor hace publico e y n
# Emisor forma el mesg, el cual es una lista de valores numericos menores que phi
# Emisor encripta cada elemento del mensaje x de la forma pot_e_mod_n(x,e,n).
# Para encriptar todo el mensaje, llamamos a rsa con la clave publica y base n, msg_encriptado = rsa(msg,e,n)
# Receptor desencripta el mensaje invocando la funcion rsa con la clave privada y base n, rsa(msg_encriptado,d,)