이산 로그¶

이산 로그는 다음 방정식을 만족하는 정수 $x$입니다

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

여기서 $a$, $b$, $m$은 주어진 정수입니다.

이산 로그가 항상 존재하는 것은 아닙니다. 예를 들어 $2^x \equiv 3 \pmod 7$에는 해가 없습니다. 이산 로그가 존재하는지 판별할 수 있는 간단한 조건은 없습니다.

이 글에서는 1971년 Shanks가 제안한 이산 로그 계산 알고리즘인 Baby-step giant-step 알고리즘을 설명합니다. 이 알고리즘의 시간 복잡도는 $O(\sqrt{m})$입니다. 이 알고리즘은 작업을 절반으로 나누는 기법을 사용하므로 중간에서 만나기(meet-in-the-middle) 알고리즘입니다.

알고리즘¶

다음 방정식을 생각해 봅시다:

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

여기서 $a$와 $m$은 서로소입니다.

$x = np - q$라고 둡시다. 여기서 $n$은 미리 선택한 상수입니다($n$을 선택하는 방법은 뒤에서 설명합니다). $p$를 1 증가시키면 $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).$$

이 문제는 다음과 같이 중간에서 만나기 방법으로 풀 수 있습니다:

가능한 모든 인자 $p$에 대해 $f_1$을 계산합니다. 값-인자 쌍의 배열을 정렬합니다.
가능한 모든 인자 $q$에 대해 $f_2$를 계산하고, 정렬된 배열에서 이진 탐색으로 대응하는 $p$를 찾습니다.

복잡도¶

이진 거듭제곱 알고리즘을 사용하면 $f_1(p)$를 $O(\log m)$에 계산할 수 있습니다. $f_2(q)$도 마찬가지입니다.

알고리즘의 첫 번째 단계에서는 가능한 모든 인자 $p$에 대해 $f_1$을 계산한 뒤 그 값들을 정렬해야 합니다. 따라서 이 단계의 복잡도는 다음과 같습니다:

$$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$ 값의 배열에서 이진 탐색을 해야 하므로, 이 단계의 복잡도는 다음과 같습니다:

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

이제 두 복잡도를 더하면 $\log m$에 $n$과 $m/n$의 합을 곱한 값이 되며, 이는 $n = m/n$일 때 최소가 됩니다. 즉, 최적의 성능을 얻으려면 $n$을 다음과 같이 선택해야 합니다:

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

그러면 알고리즘의 복잡도는 다음과 같습니다:

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

구현¶

가장 간단한 구현¶

다음 코드에서 함수 powmod는 $a^b \pmod m$을 계산하고, 함수 solve는 문제의 올바른 해를 구합니다. 해가 없으면 $-1$을 반환하고, 그렇지 않으면 가능한 해 중 하나를 반환합니다.

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

이 코드에서는 $f_1$의 값을 저장하기 위해 C++ 표준 라이브러리의 map을 사용했습니다. map은 내부적으로 레드-블랙 트리를 사용하여 값을 저장합니다. 따라서 이 코드는 배열과 이진 탐색을 사용했을 때보다 조금 느리지만, 작성하기는 훨씬 쉽습니다.

이 코드는 $0^0 = 1$이라고 가정한다는 점에 유의하십시오. 즉, 이 코드는 방정식 $0^x \equiv 1 \pmod m$의 해로 $0$을 계산하며, $0^x \equiv 0 \pmod 1$의 해로도 $0$을 계산합니다. 이는 대수학에서 자주 사용되는 관례이지만, 모든 분야에서 보편적으로 받아들여지는 것은 아닙니다. 때로는 $0^0$을 단순히 정의되지 않은 것으로 봅니다. 이 관례가 마음에 들지 않는다면 $a=0$인 경우를 따로 처리해야 합니다:

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

또 하나 주목할 점은, 같은 $f_1$ 값에 대응되는 인자 $p$가 여러 개 있을 경우 그중 하나만 저장한다는 것입니다. 여기서는 가능한 해를 하나만 반환하면 되므로 이 방식으로 충분합니다. 가능한 모든 해를 반환해야 한다면 map<int, int>를 예를 들어 map<int, vector<int>>로 바꿔야 합니다. 두 번째 단계도 그에 맞게 수정해야 합니다.

개선된 구현¶

가능한 개선 방법 중 하나는 이진 거듭제곱을 없애는 것입니다. 이는 $q$를 증가시킬 때마다 $a$를 곱하는 변수와 $p$를 증가시킬 때마다 $a^n$을 곱하는 변수를 유지하여 구현할 수 있습니다. 이렇게 바꾸어도 알고리즘의 복잡도는 동일하지만, 이제 $\log$ 인자는 map에서만 발생합니다. map 대신 삽입과 탐색의 평균 시간 복잡도가 $O(1)$인 해시 테이블(C++에서는 unordered_map)을 사용할 수도 있습니다.

문제에서는 해를 만족하는 최소의 $x$를 요구하는 경우가 많습니다.
모든 답을 구한 뒤 최솟값을 취하거나, 처음 찾은 답을 오일러 정리를 이용해 줄일 수도 있지만, 값을 계산하는 순서를 잘 정하면 처음 찾은 답이 최솟값이 되도록 보장할 수 있습니다.

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

unordered_map을 사용하면 복잡도는 $O(\sqrt{m})$입니다.

$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)$에 수행되므로, 시간 복잡도는 이전과 같이 $O(\sqrt{m})$으로 유지됩니다.