Inverso multiplicativo (aritmética modular)

En la aritmética modular, el inverso multiplicativo de un número entero n módulo p es otro entero m (módulo p) tal que el producto mn es congruente con 1 (módulo p). Esto significa que tal número m es el inverso multiplicativo en el anillo de los enteros módulo p, es decir, n^-1 ≡ m (mod p). Se habla de inverso multiplicativo para distinguirlo del elemento inverso, tal y como es entendido en teoría de grupos.

El inverso multiplicativo de n módulo p existe si y solo si n y p son coprimos, es decir, si mcd(n, p)=1. Si existe el inverso multiplicativo de un número n módulo p, entonces se puede definir la operación de división de cualquier otro número entre n módulo p, mediante la multiplicación de ese número por el inverso n^-1. Si p es un número primo, entonces todos los números excepto el cero (y sus congruentes —los múltiplos de p) son invertibles, lo que convierte al anillo de los enteros módulo p en un cuerpo.

A veces se pueden encontrar muchos valores de m para los cuales sea cierta esta congruencia. El m seleccionado como multiplicador modular inverso es generalmente el natural más pequeño posible (o simplemente el que sea miembro del conjunto Z_n en el que n sea el módulo).

Por ejemplo:

nos da

El m más pequeño que resuelve esta congruencia es 4; así pues, el multiplicador modular inverso de 3 (mod 11) es 4. Sin embargo, otro m que resuelve la congruencia es 15 (fácilmente determinable sumando p al inverso obtenido).^[1]​

El inverso multiplicativo de n módulo p se puede obtener mediante el Algoritmo de Euclides. En particular, invocando el algoritmo extendido de Euclides con n y p como argumentos se obtiene una tripla (x,y,mcd(n,p)) tal que

Si MCD(n,p)=1 entonces

de donde ${displaystyle x}$ es el inverso modular de n módulo p. Si el MCD(n,p)≠ 1 entonces no existe el modular inverso. Este algoritmo se ejecuta en un tiempo O(log(p)²) (asumiendo que |n|<p).

Por ejemplo, supongamos que queremos calcular el inverso de 117 módulo 244. Por tanto con nuestra nomenclatura (n módulo p), p=244 y n=117 Lo primero que hacemos es aplicar el algoritmo de Euclides para verificar que mcd(n,p)=1. Posteriormente aprovechamos los pasos intermedios para hallar el mcd(n,p) en términos de n y p y así obtener el inverso de n que notaremos por n^-1.

De esta forma demostramos que mcd(244,117)=1

El método de exponenciación modular directa como alternativa al algoritmo euclidiano extendido es el siguiente:

De acuerdo con el Teorema de Euler, si n es coprimo con p, es decir, MCD(n,p)=1, entonces,

Esto se deduce del Teorema de Lagrange y del hecho de que n pertenece al grupo multiplicativo de enteros módulo n ${displaystyle (mathbb {Z} /pmathbb {Z} )^{*}}$ si y sólo si n es coprimo con p.

Así pues,

donde φ(p) es la Función φ de Euler.

De esta forma se puede obtener el multiplicador modular inverso de n módulo p de forma directa:

En el caso especial en que p es primo,

Se puede usar la Exponenciación binaria para ejecutar este método de forma eficiente para lo cual se requieren solamente O(log(p)) operaciones modulares.

Si se utiliza el método escolar tradicional, el tiempo de ejecución es O(log(p)³).

Cuando se usa la multiplicación basada en FFT de Strassen, el tiempo de ejecución es O(log(p)² log(log(p))log(log(log(p)))). Este método es generalmente más lento que el algoritmo euclidiano extendido pero se usa a veces cuando ya existe una implementación de la exponenciación modular. Una desventaja de este método es que necesita φ(p) porque la única forma de computación eficiente requiere el conocimiento de los factores de p.