Ya en esta publicación se habló de lo que básicamente es el inverso modular, este post es para explicar las formas más conocidas para hallarlo.

El inverso modular de A en modulo N lo representamos como:

(i) X ≡ A^(-1) mod N
ó
(ii) X * A ≡ 1 mod N

Nos interesa el cálculo de X, del cual podemos afirmar que solo existe si MCD(A,N) = 1, es decir cuando A y N no tienen factores comunes aparte del 1.

Primero, apliquemos la propiedad de congruencia en (ii), así tenemos:

N | (X * A – 1)
Es decir el valor de X*A – 1 debe ser múltiplo de N

Es decir, existe un entero K tal que:

(α) N * K = X * A – 1

Hemos llevado la expresión (ii) a la forma de (α). Ahora veamos la primera forma de poder hallar el inverso de A en módulo N, es decir X.

1ra Forma – Método Ingenuo

Tiempo: O(N)
Espacio: O(1)

Despejamos en (α) a K:

K = (X * A – 1) / N
Dado que K es entero la división debería ser entera también

Nuestro parámetro o variable es X.
Los valores de X para los que (X * A – 1) / N no es un entero serán erróneos, mientras que el valor que haga que (X * A – 1) / N sea entero será el valor que estamos buscando.

Podemos implementar el siguiente algoritmo:

int inverse(int A, int N) {
    if (mcd(A, N) != 1) return 0; /* Inverso no existe /*
    for (int X=0; X<N; X++) {
        if ((A*X-1)%N == 0)
            return X;
    }
}

Complejidad: O(n)

El algoritmo anterior implementado en C++ comienza por comprobar la existencia del inverso y en caso no exista retorna 0, luego busca cada posible valor de X que cumpla la condición dicha anteriormente la cual podemos observar por la sentencia IF en el código.
Solo comprobamos los valores de 0 a N ya que los demás números no hacen falta comprobar ya que dichos número son congruentes (en módulo N) a algún número que ya esta en el rango de 0 a N los cuales son los que ya evaluamos.

Ahora hallemos los inversos de todos los números en módulo 7:

int main() {
    const int mod = 7;
    cout<<"MODULO "<<mod<<endl;
    for (int i=0; i<mod; i++){ 
        int inv = inverse(i, mod);
        if (inv)
            cout<<"inverso de "<<i<<": "<<inv<<endl;
        else
            cout<<"inverso de "<<i<<" ¡no existe!"<<endl;
    }
    return 0;
}

OUTPUT:
        EN MODULO 7
inverso de 0 ¡no existe!
inverso de 1: 1
inverso de 2: 4
inverso de 3: 5
inverso de 4: 2
inverso de 5: 3
inverso de 6: 6

Podemos ver en la salida que el inverso de 0 no existe, lo cual es cierto como se vio en esta publicación, luego tenemos los inversos de 1, 2, 3, 4, 5 y 6 los cuales es fácil notar que existen, dado que 7 es número primo por lo que el MCD con cualquier otro número (no múltiplo de 7) será 1, por lo que todos los números en módulo 7 tienen inverso, esto no es asi con los números no primos como el 9, ya que por ejemplo en módulo 9 no existen los inversos para 0, 3, 6:

        EN MODULO 9
inverso de 0 no existe!
inverso de 1: 1
inverso de 2: 5
inverso de 3 no existe!
inverso de 4: 7
inverso de 5: 2
inverso de 6 no existe!
inverso de 7: 4
inverso de 8: 8

Este algoritmo para hallar el inverso funciona y en una complejidad lineal O(n), sin embargo para números mucho más grandes esta complejidad lineal puede terminar siendo demasiado lenta, podemos ajustar esto hasta una complejidad logarítmica:

2da Forma – Algoritmo Extendido de Euclides

Tiempo: O(log N)
Espacio: O(1)

El algoritmo extendido de Euclides se explica en este post, el cual se muestra a continuación para ser usado en el cálculo de el inverso modular:

#include <iostream>
#include <tuple>

std::tuple<int,int,int> extended_euclidean(int a, int b) {

    int r0 = a>b? a:b;
    int r1 = r0==a? b:a;
    int s0=1, s1=0, t0=0, t1=1;

    while (r1 != 0) {
        int r = r0 % r1;
        int q = int(r0/r1);
        int s = s0 - q * s1;
        int t = t0 - q * t1;

        r0 = r1;
        r1 = r;
        s0 = s1;
        s1 = s;
        t0 = t1;
        t1 = t;
    }

    return std::make_tuple(r0, s0, t0);
}

int inverse_mod(int n, int m) {
    int mcd, s, t;
    std::tie(mcd, s, t) = extended_euclidean(n, m);
    if (mcd != 1)
        throw std::overflow_error("GCD is not one, inverse modular doesn't exist\n");
    return n<m? t%m:s%m;
}

Probamos el algoritmo:

int main() {
    int mcd, s, t;
    int a=4013, b=4057;
    std::tie(mcd, s, t)= extended_euclidean(a,b);
    printf("\t.::Bezout Coeficients::.\n");
    printf("MCD(%d, %d) = %d = %d*(%d) + %d*(%d) \n", a,b,mcd,a,s,b,t);

    printf("\t.:: 4013^(-1) mod 4057 ::.\n");
    printf(" = %d\n", inverse_mod(4013, 4057));

    printf("\t.:: 4057^(-1) mod 4013 ::.\n");
    printf(" = %d\n", inverse_mod(4057, 4013));

    printf("\t.:: 2^(-1) mod 4 ::.\n");
    try {
        printf(" = %d\n", inverse_mod(2, 4));
    } catch (std::overflow_error e) {
        std::cout << e.what() ;
    }

    printf("\t.:: END ::.");

}

OUTPUT
        .::Bezout Coeficients::.
MCD(4013, 4057) = 1 = 4013*(-456) + 4057*(461)
        .:: 4013^(-1) mod 4057 ::.
 = 461
        .:: 4057^(-1) mod 4013 ::.
 = -456
        .:: 2^(-1) mod 4 ::.
GCD is not one, inverse modular doesn't exist
        .:: END ::.