Inverso multiplicativo modulo n

El inverso multiplicativo de un entero modulo n es el residuo inverse que cumple que el entero por ese inverse es congruente con uno modulo n. Ese inverse existe si y solo si el entero y el módulo son coprimos: su máximo común divisor vale uno. Los tutoriales de criptografía, los pasos de clave privada RSA, la división modular en programación competitiva y los cálculos en grupos cíclicos necesitan esta operación, pero muchos lenguajes solo exponen un GCD binario y dejan a usted los coeficientes de Bézout.

Qué es un inverso multiplicativo modulo n y cuándo existe

En la aritmética ordinaria todo número no nulo tiene inverso multiplicativo: al dividir por él se obtiene uno. En aritmética modular la misma idea se convierte en una congruencia. Decimos que inverse es un inverso multiplicativo de un entero modulo n cuando el entero por inverse deja resto uno al dividir por el módulo.

Como los residuos se reinician cada n pasos, no todo entero posee tal inverse. El obstáculo es aritmético, no de punto flotante: si d es el gcd del entero y del módulo y d es mayor que uno, entonces el entero por cualquier candidato es múltiplo de d, de modo que el producto nunca puede ser congruente con uno, que no es múltiplo de d.

A la inversa, la identidad de Bézout garantiza enteros x e y con entero por x más módulo por y igual a uno exactamente cuando ese gcd vale uno, y reducir x modulo n produce el inverse. Los ingenieros encuentran esta condición al dividir en un anillo finito, al elegir exponentes de descifrado RSA que invierten el exponente público modulo phi de N, al deshacer multiplicaciones modulares en tuberías de hash o al resolver congruencias lineales en programación competitiva.

Devolver un error explícito cuando el par no es coprimo es más útil que un fallo silencioso: el cliente aprende que no existe inverse y puede ramificar según el gcd en lugar de adivinar qué biblioteca devolvió un residuo incorrecto. La calculadora trata por tanto un par no coprimo como entrada inválida, en vez de inventar un inverse ficticio que rompería cualquier comprobación posterior de la congruencia definitoria.

Cómo esta calculadora ejecuta el algoritmo de Euclides extendido

La implementación reduce primero el entero a la clase de residuo no negativa residue entre cero y n menos uno, y luego aplica el algoritmo de Euclides extendido al par residue y modulus. Cada paso registra el cociente entero y actualiza los coeficientes de Bézout de modo que, al terminar, el coeficiente de residue por residue más un coeficiente del módulo iguala el gcd. Si el gcd es uno, el coeficiente de residue se reduce al intervalo de cero a n menos uno y se devuelve como inverse.

Los valores absolutos están acotados por un billón para que todo doblado intermedio del producto modular quede dentro del rango de enteros seguros de JavaScript. Se aceptan enteros negativos y se reducen antes del bucle euclidiano, así que una entrada de menos tres modulo once se trata como residue ocho y se invierte en esa clase.

Uso práctico, límites, precios y entrega

Use la herramienta del navegador cuando desee un inverse rápido al leer una nota de cripto, comprobar una congruencia de tarea o depurar un paso de multiplicación modular. Las entradas aceptadas son enteros cuyo valor absoluto es como máximo un billón y módulos de dos a un billón. Los resultados son deterministas: el mismo par siempre produce el mismo inverse y el mismo campo check.

Mantenga el par dentro de los límites publicados, trate el error de no coprimos como un resultado de primera clase en sus pruebas y obtendrá un inverse reproducible para deberes, complementos LMS y workers en el borde sin montar un sistema de álgebra computacional propio.