Logaritmo discreto

El logaritmo discreto es un entero $x$ que satisface la ecuación

$a^x \equiv b \pmod m$

para enteros dados $a$ , $b$ y $m$ .

El logaritmo discreto no siempre existe; por ejemplo, no hay solución de $2^x \equiv 3 \pmod 7$ . No hay una condición sencilla para determinar si el logaritmo discreto existe.

En este artículo describimos el algoritmo Baby-step giant-step (pasos de bebé y de gigante), un algoritmo para calcular el logaritmo discreto propuesto por Shanks en 1971, que tiene complejidad temporal $O(\sqrt{m})$ . Es un algoritmo de meet-in-the-middle porque usa la técnica de separar las tareas por la mitad.

Algoritmo

Consideremos la ecuación:

$a^x \equiv b \pmod m,$

donde $a$ y $m$ son coprimos.

Sea $x = np - q$ , donde $n$ es alguna constante preseleccionada (más adelante describiremos cómo elegir $n$ ). $p$ se conoce como paso gigante (giant step), ya que incrementarlo en uno incrementa $x$ en $n$ . De forma análoga, $q$ se conoce como paso bebé (baby step).

Obviamente, cualquier número $x$ en el intervalo $[0; m)$ se puede representar de esta forma, donde $p \in [1; \lceil \frac{m}{n} \rceil ]$ y $q \in [0; n]$ .

Entonces la ecuación queda:

$a^{np - q} \equiv b \pmod m.$

Usando el hecho de que $a$ y $m$ son coprimos, obtenemos:

$a^{np} \equiv ba^q \pmod m$

Esta nueva ecuación se puede reescribir de forma simplificada:

$f_1(p) = f_2(q).$

Este problema se puede resolver con el método meet-in-the-middle de la siguiente manera:

Calcular $f_1$ para todos los argumentos posibles $p$ . Ordenar el arreglo de pares valor-argumento.
Para todos los argumentos posibles $q$ , calcular $f_2$ y buscar el $p$ correspondiente en el arreglo ordenado usando búsqueda binaria.

Complejidad

Podemos calcular $f_1(p)$ en $O(\log m)$ usando el algoritmo de exponenciación binaria. De forma análoga para $f_2(q)$ .

En el primer paso del algoritmo, hay que calcular $f_1$ para cada argumento posible $p$ y luego ordenar los valores. Así, este paso tiene complejidad:

$O\left(\left\lceil \frac{m}{n} \right\rceil \left(\log m + \log \left\lceil \frac{m}{n} \right\rceil \right)\right) = O\left( \left\lceil \frac {m}{n} \right\rceil \log m\right)$

En el segundo paso del algoritmo, hay que calcular $f_2(q)$ para cada argumento posible $q$ y luego hacer una búsqueda binaria sobre el arreglo de valores de $f_1$ ; así, este paso tiene complejidad:

$O\left(n \left(\log m + \log \frac{m}{n} \right) \right) = O\left(n \log m\right).$

Ahora, al sumar estas dos complejidades, obtenemos $\log m$ multiplicado por la suma de $n$ y $m/n$ , que es mínima cuando $n = m/n$ , lo que significa que, para alcanzar el rendimiento óptimo, $n$ debe elegirse de modo que:

$n = \sqrt{m}.$

Entonces la complejidad del algoritmo queda:

$O(\sqrt {m} \log m).$

Implementación

La implementación más simple

En el siguiente código, la función powmod calcula $a^b \pmod m$ y la función solve produce una solución adecuada del problema. Devuelve $-1$ si no hay solución y, en caso contrario, devuelve una de las soluciones posibles.


int powmod(int a, int b, int m) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * 1ll * a) % m;
        }
        a = (a * 1ll * a) % m;
        b >>= 1;
    }
    return res;
}
 
int solve(int a, int b, int m) {
    a %= m, b %= m;
    int n = sqrt(m) + 1;
    map<int, int> vals;
    for (int p = 1; p <= n; ++p)
        vals[powmod(a, p * n, m)] = p;
    for (int q = 0; q <= n; ++q) {
        int cur = (powmod(a, q, m) * 1ll * b) % m;
        if (vals.count(cur)) {
            int ans = vals[cur] * n - q;
            return ans;
        }
    }
    return -1;
}

En este código usamos map de la biblioteca estándar de C++ para almacenar los valores de $f_1$ . Internamente, map usa un árbol rojo-negro para guardar los valores. Así, este código es un poco más lento que si hubiéramos usado un arreglo y búsqueda binaria, pero es mucho más fácil de escribir.

Nótese que nuestro código asume $0^0 = 1$ , es decir, el código calculará $0$ como solución de la ecuación $0^x \equiv 1 \pmod m$ y también como solución de $0^x \equiv 0 \pmod 1$ . Esta es una convención usada a menudo en álgebra, pero no está universalmente aceptada en todas las áreas. A veces $0^0$ simplemente no está definido. Si no se comparte esa convención, hay que tratar el caso $a=0$ por separado:


    if (a == 0)
        return b == 0 ? 1 : -1;

Otra cosa a notar es que, si hay varios argumentos $p$ que corresponden al mismo valor de $f_1$ , solo almacenamos uno de esos argumentos. Esto funciona en este caso porque solo queremos devolver una solución posible. Si necesitamos devolver todas las soluciones posibles, hay que cambiar map<int, int> por, por ejemplo, map<int, vector<int>>. También hay que cambiar el segundo paso de forma correspondiente.

Implementación mejorada

Una posible mejora es deshacerse de la exponenciación binaria. Esto se puede hacer manteniendo una variable que se multiplica por $a$ cada vez que incrementamos $q$ y una variable que se multiplica por $a^n$ cada vez que incrementamos $p$ . Con este cambio, la complejidad del algoritmo sigue siendo la misma, pero ahora el factor $\log$ es solo por el map. En lugar de un map, también podemos usar una tabla hash (unordered_map en C++), que tiene complejidad temporal promedio $O(1)$ para insertar y buscar.

Los problemas a menudo piden el mínimo $x$ que satisface la solución.
Es posible obtener todas las respuestas y tomar el mínimo, o reducir la primera respuesta encontrada usando el teorema de Euler, pero podemos ser inteligentes con el orden en que calculamos los valores y asegurar que la primera respuesta que encontremos sea la mínima.


// Devuelve el mínimo x para el cual a ^ x % m = b % m; a y m son coprimos.
int solve(int a, int b, int m) {
    a %= m, b %= m;
    int n = sqrt(m) + 1;

    int an = 1;
    for (int i = 0; i < n; ++i)
        an = (an * 1ll * a) % m;

    unordered_map<int, int> vals;
    for (int q = 0, cur = b; q <= n; ++q) {
        vals[cur] = q;
        cur = (cur * 1ll * a) % m;
    }

    for (int p = 1, cur = 1; p <= n; ++p) {
        cur = (cur * 1ll * an) % m;
        if (vals.count(cur)) {
            int ans = n * p - vals[cur];
            return ans;
        }
    }
    return -1;
}

La complejidad es $O(\sqrt{m})$ usando unordered_map.

Cuando $a$ y $m$ no son coprimos { data-toc-label=‘Cuando a y m no son coprimos’ }

Sea $g = \gcd(a, m)$ , y $g > 1$ . Claramente $a^x \bmod m$ para todo $x \ge 1$ será divisible por $g$ .

Si $g \nmid b$ , no hay solución para $x$ .

Si $g \mid b$ , sean $a = g \alpha, b = g \beta, m = g \nu$ .

$\begin{aligned} a^{x} & \equiv b m o d m \\ (g α) a^{x - 1} & \equiv g β m o d g ν \\ α a^{x - 1} & \equiv β m o d ν \end{aligned}$

El algoritmo baby-step giant-step se puede extender fácilmente para resolver $ka^{x} \equiv b \pmod m$ para $x$ .


// Devuelve el mínimo x para el cual a ^ x % m = b % m.
int solve(int a, int b, int m) {
    a %= m, b %= m;
    int k = 1, add = 0, g;
    while ((g = gcd(a, m)) > 1) {
        if (b == k)
            return add;
        if (b % g)
            return -1;
        b /= g, m /= g, ++add;
        k = (k * 1ll * a / g) % m;
    }

    int n = sqrt(m) + 1;
    int an = 1;
    for (int i = 0; i < n; ++i)
        an = (an * 1ll * a) % m;

    unordered_map<int, int> vals;
    for (int q = 0, cur = b; q <= n; ++q) {
        vals[cur] = q;
        cur = (cur * 1ll * a) % m;
    }

    for (int p = 1, cur = k; p <= n; ++p) {
        cur = (cur * 1ll * an) % m;
        if (vals.count(cur)) {
            int ans = n * p - vals[cur] + add;
            return ans;
        }
    }
    return -1;
}

La complejidad temporal sigue siendo $O(\sqrt{m})$ como antes, ya que la reducción inicial a $a$ y $m$ coprimos se hace en $O(\log^2 m)$ .

Problemas de práctica

Spoj - Power Modulo Inverted
Topcoder - SplittingFoxes3
CodeChef - Inverse of a Function
Hard Equation (asume que $0^0$ no está definido)
CodeChef - Chef and Modular Sequence