Inverso modular

Un entero positivo multiplicado por su inverso siempre es igual a 1: 17*(1/17)==1. En la aritmética modular existe un concepto similar de inverso, aunque, para el módulo m, estamos limitados a los enteros del 0 al m-1. El inverso multiplicativo modular de 3 módulo 5 es igual a 2 porque (3*2)%5==1. Otro ejemplo: el inverso modular de 17 módulo 1000007 es igual a 58824 porque (17*58824)%1000007==1. El inverso modular, si existe, siempre debe estar en el rango de 0 a m-1.

Crea una función cuyos argumentos sean el entero n y el módulo m. La función devolverá el inverso modular de n mod m. Si el inverso modular no existe, devuelve false.

Ejemplos

mod_inv(2, 3) ➞ 2

mod_inv(12, 47) ➞ 4

mod_inv(11, 33) ➞ false

mod_inv(55, 678) ➞ 37

mod_inv(81, 3455) ➞ 2346

Notas

• Algunos casos de prueba tienen enteros bastante grandes, por lo que, si intentas buscar por fuerza bruta en todo el campo modular, es posible que no tengas éxito debido al límite de tiempo de 12 segundos impuesto por el servidor. Consulta Recursos para conocer un enfoque más eficiente.
• El inverso modular de un número n módulo m existe únicamente si n y m son coprimos (es decir, no tienen factores comunes aparte de 1).
• Un uso práctico del inverso modular se encuentra en la criptografía de clave pública, como RSA, donde puede utilizarse para determinar el valor de la clave privada.