#!/usr/bin/python
# INVERSO MULTIPLICATIVO MODULAR
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception("No existe el inverso modular") # SI NO EXISTE, DEVUELVE ERROR
else:
return x % m
print
print "Ejemplo. El inverso multiplicador del numero 63 en modulo 26 es 19."
print modinv(63, 26) # ESTA OPERACION DA 19
print
valor1 = input("Ingresa el numero: ")
valor2 = input("Ingresa el modulo: ")
print
print "El INV. MULT. MODUL. del valor introducido en el modulo introducido es: ", modinv(valor1, valor2)
print
# =================== SEGUNDA FUNCION =================
# FUNCION LAMBDA
MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1]
# DEVOLVERA (-1) SI EL VALOR (A) NO TIENE INVERSO MULTIPLICATIVO EN (N)
# USO
# MMI(23, 99) DEVUELVE 56
# MMI(18, 24) DEVUELVE -1
print MMI(23, 99)
print MMI(18, 24)
# ================== TERCERA FUNCION =================
def imod(a, n):
c = 1
while (c % a > 0):
c += n
return c // a
print imod(63, 26) # RESULTADO 19. SI NO HAY INVERSO MULTIPLICATIVO SE QUEDA EN BLANCO.
# ==================== CUARTA FUNCION ====================
# COMO HAY TANTAS FUNCIONES DEJO EL ENLACE DE LA PAGINA DONDE LAS HE SACADO
# https://www.it-swarm.dev/es/python/funcion-inversa-multiplicativa-modular-en-python/972004398/
# FUNCION BASADA EN ALGORITMO DE EUCLIDES
def multiplicative_inverse(a, b):
origA = a
X = 0
prevX = 1
Y = 1
prevY = 0
while b != 0:
temp = b
quotient = a/b
b = a%b
a = temp
temp = X
a = prevX - quotient * X
prevX = temp
temp = Y
Y = prevY - quotient * Y
prevY = temp
return origA + prevY
print multiplicative_inverse(59, 26) # NO SE QUE PASA. DA 60 Y DEBERIA DAR 15 !!! ojo !!!
# ==================== QUINTA FUNCION ==================
def find_mod_inv(a,m):
for x in range(1,m):
if((a%m)*(x%m) % m==1):
return x
raise Exception("El inverso modular no existe.")
#a = 13
#m = 22
a = int(input("Introduce numero: "))
m = int(input("Introduce modulo: "))
try:
res=find_mod_inv(a,m)
print("El Inverso Multiplicativo Modular es: "+ str(res))
except:
print('El inverso modular no existe.')
# ================ SEXTA FUNCION ===================
# USAMOS LA FUNCION INCORPORADA EN PYTHON -pow-
print
print "Usamos la funcion de python -pow-"
print
a = 38
m = 97
res = pow(a, m-2, m)
print "El inverso multiplicativo modular es: " + str(res)
print
Ejemplo. El inverso multiplicador del numero 63 en modulo 26 es 19.
19
Ingresa el numero: 145
Ingresa el modulo: 26
El INV. MULT. MODUL. del valor introducido en el modulo introducido es: 7
56
-1
19
60
Introduce numero: 196
Introduce modulo: 26
El inverso modular no existe.
Usamos la funcion de python -pow-
El inverso multiplicativo modular es: 23