Дискрет логарифм¶

Дискрет логарифм гэдэг нь өгөгдсөн бүхэл тоо $a$, $b$ ба $m$-ийн хувьд

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

тэгшитгэлийг хангах бүхэл тоо $x$ юм.

Дискрет логарифм үргэлж оршдоггүй, жишээ нь $2^x \equiv 3 \pmod 7$ шийдгүй. Дискрет логарифм оршин байгаа эсэхийг тодорхойлох энгийн нөхцөл байдаггүй.

Энэ өгүүлэлд бид 1971 онд Шанксын дэвшүүлсэн, дискрет логарифмыг тооцоолох $O(\sqrt{m})$ time complexity-тэй Baby-step giant-step алгоритмыг тайлбарлана. Энэ нь бодлогыг хоёр хуваах техник ашигладаг тул meet-in-the-middle алгоритм юм.

Алгоритм¶

Дараах тэгшитгэлийг авч үзье:

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

энд $a$ ба $m$ харилцан анхны.

$x = np - q$ гэе, энд $n$ нь урьдчилан сонгосон ямар нэг тогтмол (үүнийг хэрхэн сонгохыг дараа тайлбарлана). $p$-г нэгээр нэмэгдүүлэхэд $x$ нь $n$-ээр нэмэгддэг тул $p$-г giant step гэж нэрлэдэг. Үүнтэй адилаар $q$-г baby step гэж нэрлэдэг.

$[0; m)$ интервал дахь дурын тоо $x$-г $p \in [1; \lceil \frac{m}{n} \rceil ]$ ба $q \in [0; n]$-тэйгээр энэ хэлбэрээр илэрхийлж болох нь ойлгомжтой.

Тэгвэл тэгшитгэл дараах хэлбэртэй болно:

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

$a$ ба $m$ харилцан анхны гэдгийг ашиглан бид дараахыг авна:

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

Энэ шинэ тэгшитгэлийг хялбарчилсан хэлбэрээр дахин бичиж болно:

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

Энэ бодлогыг meet-in-the-middle аргаар дараах байдлаар бодож болно:

Бүх боломжит аргумент $p$-ийн хувьд $f_1$-г тооцоол. Утга-аргументийн хосуудын массивыг эрэмбэл.
Бүх боломжит аргумент $q$-ийн хувьд $f_2$-г тооцоолж, эрэмбэлсэн массиваас хоёртын хайлт ашиглан харгалзах $p$-г хай.

Complexity¶

Бид хоёртын зэрэгт дэвшүүлэлтийн алгоритм ашиглан $f_1(p)$-г $O(\log m)$-д тооцоолж болно. $f_2(q)$-ийн хувьд ч мөн адил.

Алгоритмын эхний алхамд бид боломжит аргумент $p$ бүрийн хувьд $f_1$-г тооцоолж, дараа нь утгуудыг эрэмбэлэх хэрэгтэй. Тиймээс энэ алхам дараах complexity-тэй:

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

Алгоритмын хоёр дахь алхамд бид боломжит аргумент $q$ бүрийн хувьд $f_2(q)$-г тооцоолж, дараа нь $f_1$-ийн утгуудын массив дээр хоёртын хайлт хийх хэрэгтэй тул энэ алхам дараах complexity-тэй:

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

Одоо эдгээр хоёр complexity-г нэмбэл $n$ ба $m/n$-ийн нийлбэрээр үржүүлсэн $\log m$ гарах бөгөөд энэ нь $n = m/n$ үед хамгийн бага байна, өөрөөр хэлбэл оновчтой гүйцэтгэлд хүрэхийн тулд $n$-г дараах байдлаар сонгох ёстой:

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

Тэгвэл алгоритмын complexity дараах байдалтай болно:

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

Implementation¶

The simplest implementation¶

In the following code, the function powmod calculates $a^b \pmod m$ and the function solve produces a proper solution to the problem. It returns $-1$ if there is no solution and returns one of the possible solutions otherwise.

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;
}

In this code, we used map from the C++ standard library to store the values of $f_1$. Internally, map uses a red-black tree to store values. Thus this code is a little bit slower than if we had used an array and binary searched, but is much easier to write.

Notice that our code assumes $0^0 = 1$, i.e. the code will compute $0$ as solution for the equation $0^x \equiv 1 \pmod m$ and also as solution for $0^x \equiv 0 \pmod 1$. This is an often used convention in algebra, but it's also not universally accepted in all areas. Sometimes $0^0$ is simply undefined. If you don't like our convention, then you need to handle the case $a=0$ separately:

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

Another thing to note is that, if there are multiple arguments $p$ that map to the same value of $f_1$, we only store one such argument. This works in this case because we only want to return one possible solution. If we need to return all possible solutions, we need to change map<int, int> to, say, map<int, vector<int>>. We also need to change the second step accordingly.

Improved implementation¶

A possible improvement is to get rid of binary exponentiation. This can be done by keeping a variable that is multiplied by $a$ each time we increase $q$ and a variable that is multiplied by $a^n$ each time we increase $p$. With this change, the complexity of the algorithm is still the same, but now the $\log$ factor is only for the map. Instead of a map, we can also use a hash table (unordered_map in C++) which has the average time complexity $O(1)$ for inserting and searching.

Problems often ask for the minimum $x$ which satisfies the solution.
It is possible to get all answers and take the minimum, or reduce the first found answer using Euler's theorem, but we can be smart about the order in which we calculate values and ensure the first answer we find is the minimum.

// Returns minimum x for which a ^ x % m = b % m, a and m are coprime.
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;
}

The complexity is $O(\sqrt{m})$ using unordered_map.

$a$ ба $m$ харилцан анхны биш үед¶

$g = \gcd(a, m)$ ба $g > 1$ гэе. Бүх $x \ge 1$-ийн хувьд $a^x \bmod m$ нь $g$-д хуваагдах нь тодорхой.

Хэрэв $g \nmid b$ бол $x$-ийн шийд байхгүй.

Хэрэв $g \mid b$ бол $a = g \alpha, b = g \beta, m = g \nu$ гэе.

$$ \begin{aligned} a^x & \equiv b \mod m \\\ (g \alpha) a^{x - 1} & \equiv g \beta \mod g \nu \\\ \alpha a^{x-1} & \equiv \beta \mod \nu \end{aligned} $$

Baby-step giant-step алгоритмыг $x$-ийн хувьд $ka^{x} \equiv b \pmod m$-г бодохоор амархан өргөтгөж болно.

// Returns minimum x for which 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;
}

Харилцан анхны $a$ ба $m$ рүү анхны хураалт $O(\log^2 m)$-д хийгддэг тул time complexity өмнөхтэй адил $O(\sqrt{m})$ хэвээр байна.

Дасгал бодлогууд¶

Spoj - Power Modulo Inverted
Topcoder - SplittingFoxes3
CodeChef - Inverse of a Function
Hard Equation ($0^0$ тодорхойгүй гэж үзнэ)
CodeChef - Chef and Modular Sequence