Logaritmo discreto

O logaritmo discreto é um número inteiro $x$ resolvendo a equação

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

onde $a$ e $m$ são coprimos. Nota, se eles não forem relativamente primos, então o algoritmo descrito abaixo está incorreto, embora possa ser modificado para funcionar.

Neste artigo, descrevemos o algoritmo "Baby step - giant step", proposto por Shanks em 1971, que tem a complexidade de tempo $O(\sqrt{m} \log m)$. Esse algoritmo também é conhecido como "meet-in-the-middle" porque usa a técnica de separar tarefas pela metade.

Algoritmo

Considere a equação:

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

onde $a$ e $m$ são coprimos.

Seja $x = np - q$, onde $n$ é alguma constante pré-selecionada (iremos descrever como selecionar $n$ depois). $p$ é conhecido como o "giant step", já que aumentá-lo em um aumenta $x$ em $n$. Similarmente, $q$ é conhecido como o "baby step".

Obviamente, qualquer número $x$ no intervalo $[0; m)$ pode ser representado nessa forma, onde $p \in [1; \lceil \frac{m}{n} \rceil ]$ e $q \in [0; n]$.

Então, a equação se torna:

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

Usando o fato que $a$ e $m$ são coprimos, obtemos:

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

Esta nova equação pode ser reescrita de uma forma simplificada:

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

Esse problema pode ser resolvido usando o método meet-in-the-middle, da seguinte maneira:

Complexidade

Podemos calcular $f_1(p)$ em $O(\log m)$ usando exponenciação binária. Similar para $f_2(q)$.

Na primeira etapa do algoritmo, precisamos calcular $f_1$ para cada argumento possível $p$ e então, ordenar os valores. Portanto, essa etapa tem complexidade:

$$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)$$

Na segunda etapa do algoritmo, precisamos calcular $f_2(q)$ para todos os argumentos possíveis $q$ e, em seguida, fazer uma pesquisa binária na array de valores de $f_1$, portanto, essa etapa tem complexidade:

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

Agora, quando adicionamos essas duas complexidades, obtemos $\log m$ multiplicado pela soma de $n$ e $m/n$, que é mínimo quando $n = m/n$, ou seja, para obter o desempenho ideal, $n$ deve ser escolhido de forma que:

$$n = \sqrt{m}.$$

Então, a complexidade do algoritmo se torna:

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

Implementação

Implementação simplificada

No código a seguir, a função powmod calcula $a^b \pmod m$ e a função solve produz uma solução adequada para o problema. Retorna $-1$ se não houver solução e, caso contrário, retorna uma das soluções possíveis. O logaritmo discreto resultante pode ser grande, mas você pode reduzi-lo usando o o teorema de Euler.

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) {
    int n = (int) sqrt (m + .0) + 1;
    map<int, int> vals;
    for (int p = n; p >= 1; --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;
}

Nesse código, usamos o map da biblioteca padrão C ++ para armazenar os valores de $f_1$. Internamente, o map usa uma "red-black tree"(árvore rubro-negra) para armazenar valores. Portanto, esse código é um pouco mais lento do que se tivéssemos usado uma array e uma busca binária, mas é muito mais fácil de escrever.

Outro aspecto a ser observado é que, se houver vários argumentos $p$ que mapeiam para o mesmo valor de $f_1$, armazenamos apenas um desses argumentos. Isso funciona neste caso, porque queremos apenas retornar uma solução possível. Se precisarmos retornar todas as soluções possíveis, precisamos alterar o map<int, int> para, digamos map<int, vector<int>>. Também precisamos alterar o segundo passo de acordo.

Implementação aprimorada

Uma possível melhoria é se livrar da exponenciação binária. Isso pode ser feito mantendo uma variável que é multiplicada por $a$ cada vez que $q$ é incrementado e uma variável multiplicada por $a^n$ cada vez que $p$ é incrementado. Com essa alteração, a complexidade do algoritmo ainda é a mesma, mas agora o fator $\log$ é apenas para o map. Em vez de map, também podemos usar uma hash table (unordered_map no C++) que possui a complexidade média de tempo $O(1)$ para inserir e pesquisar.

int solve(int a, int b, int m) {
    int n = (int) sqrt (m + .0) + 1;

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

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

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

Problemas