71. Order & Discrete Logarithm

 

모듈러 산술이 사용되는 이산 구조에서의 추가적인 연산에 대해 알아본다.

---

서로소인 두 정수 $a, m$와 양의 정수 $k$에 대해 $a^k \equiv 1 \pmod{m}$이고 $k$보다 작은 임의의 양의 정수 $k'$에 대해 $a^{k'} \not\equiv 1 \pmod{m}$일 때 $k$를 모듈러 $m$에 대한 $a$의 위수(Order)라고 하며 기호로는 $\text{ord}_m(a)$로 나타낸다. 오일러 토션트 함수의 성질에 의하면 $a^{\phi(m)} \equiv 1 \pmod{m}$이므로  $a$의 위수 $k$는 $\phi(m)$보다 커질 수 없으며 조금 더 확장하면 $k$는 $\phi(m)$의 약수가 되어야 한다.

 

모듈러 $m$에 대한 $a$의 위수가 $\phi(m)$일 때 $a$를 모듈러 $m$에 대한 원시근(Primitive Root)이라고 한다. $a$가 모듈러 $m$에 대한 원시근일 때, $a^1, a^2, \ldots, a^{\phi(m)}$을 $m$으로 나눈 나머지는 모두 다르며 각각의 나머지는 $m$과 서로소이다. 증명은 다음과 같이 할 수 있다.

각각의 나머지가 $m$과 서로소라는 사실은 $a$에 $m$의 소인수가 하나도 곱해지지 않았다는 사실에서 쉽게 알 수 있다. 각각의 나머지가 서로 다르다는 사실은 다음과 같이 증명이 가능하다.

$x, y$가 $\phi(m)$ 이하의 양의 정수이고 $x < y, a^x \equiv a^y \pmod{m}$이라고 하면 $\gcd(a, m) = 1$이므로 $a^{y-x} \equiv 1 \pmod{m}$이다. 이때 $y-x < \phi(m)$이고, 이것은 $\text{ord}_m(a) = \phi(m)$이라는 사실과 모순이다. 따라서 위의 식을 만족하는 쌍 $x, y$는 존재하지 않으며, 이는 각각의 나머지가 서로 다르다는 것을 의미한다.

 

원시근을 갖는 정수는 $2, 4, p^k$이다. ($p$는 홀수 소수, $k$는 양의 정수) 이 글에서는 이에 대한 증명 전체를 다루지 않지만, 일부 정수의 경우 원시근의 존재 여부를 확인하는 방법이 어렵지 않으므로 다루었다.

• $m = 2$인 경우와 $m = 4$인 경우는 직접 계산하자. $m$이 $4$일 때는 $3$이 원시근이다.
• 임의의 홀수 $x$에 대해 $x^2$을 $8$로 나눈 나머지는 $1$이므로 $m$이 $8$의 배수일 경우 원시근이 존재하지 않는다.
• $m$이 서로 다른 두 홀수 소수 $x, y$의 공배수일 경우 다음과 같은 방법으로 원시근이 존재하지 않음을 보일 수 있다. $m$보다 작은 양의 정수 $a$가 $m$의 원시근이라고 가정하면, $\text{ord}_x(a) = x-1, \text{ord}_y(a) = y-1$이다. 이때 $a$가 $m$의 원시근이므로 $\text{ord}_{xy}(a) = (x-1)(y-1)$이어야 하고, 이것은 $\text{lcm}(x-1, y-1) = (x-1)(y-1)$을 의미한다. 따라서 $x-1$과 $y-1$이 서로소여야 하는데, $x-1$과 $y-1$이 모두 짝수이므로 서로소가 될 수 없다. 이것은 $a$가 $m$의 원시근이라는 처음의 가정이 잘못되었음을 의미한다.

 

$m$이 원시근을 갖는다면 원시근의 개수는 $\phi(\phi(m))$이다. 이에 대한 증명은 참고 링크의 블로그 2에서 확인할 수 있다.

 

원시근을 빠르게 찾는 확실한 방법에 대해서는 아직도 연구가 진행중이지만, 원시근이 존재하는 경우 그 개수가 충분히 많다고 할 수 있으므로 $m$ 미만의 임의의 양의 정수를 하나 고른 뒤 그 수가 $m$의 원시근인지 확인하는 과정을 반복하면 높은 확률로 원시근을 빠르게 찾을 수 있다. 고른 수가 $m$의 원시근인지 확인하기 위해서는 위수를 계산하면 되며, 위수를 계산하는 방법은 참고 링크의 블로그 1에서 확인할 수 있다.

---

원시근에 대한 정의를 바탕으로 이산 로그(Discrete Logarithm)를 정의할 수 있다. $a$가 $m$의 원시근이고 $a^k \equiv p \pmod{m}$일 때 $k$를 나머지 변수에 대해서 나타내면 일반적인 로그 형태가 되는데 모듈러 산술이 사용되는 이산 구조의 로그이므로 이를 이산 로그라고 하고 $k = \text{ind}_a p$로 나타낸다.

 

이산 로그를 구하는 방법 중 하나인 아기걸음 거인걸음(Baby-Step Giant-Step Algorithm, BSGS)에 대해서 소개하면서 이번 글을 마무리하려고 한다. 목표는 $a^k \equiv p \pmod{m}$이고 $a, p, m$이 주어졌을 때 $k$를 구하는 것인데, $m$이 작은 경우 $a$를 계속 곱해 나가면서 $k$를 구할 수도 있지만 시간복잡도가 $\Theta(m)$이므로 $m$이 $10^9$ 정도로 커지면 속도가 너무 느려진다. Baby-Step Giant-Step Algorithm은 제곱근 분할법과 유사한 중간 만남 기법을 이용해서 시간복잡도를 $\Theta(\sqrt{m}\text{ lg }m)$으로 줄인다. (로그는 마지막에 서로 같은 값의 쌍을 찾는 과정에서 붙는다.) 먼저 $\lceil \sqrt{m} \rceil = v$라고 하면, 이산 로그가 존재할 경우 $m$보다 작은 양의 정수 $k$가 항상 존재하므로 $k = iv + j$로 나타낼 수 있다. $(0 \le i, j < v)$ 이것을 처음 식에 대입한 다음 식을 변형하면 다음과 같이 된다.

$$a^{iv+j} \equiv p \pmod{m}$$

$$a^{iv} \equiv pa^{-j} \pmod{m}$$

$$(a^v)^i \equiv p(a^{-1})^j \pmod{m}$$

이제 $i$가 $0, 1, \ldots, v-1$일 때 $(a^v)^i \,\bmod\, m$의 값과 $j$가 $0, 1, \ldots, v-1$일 때 $p(a^{-1})^j \,\bmod\, m$의 값을 모두 구한 다음 양쪽에서 서로 같은 값이 나오는 경우를 찾는다. std::map에 저장한 다음 찾는 것이 알기 쉽다. $i$가 최대한 작게, $i$가 같다면 $j$가 최대한 작은 쌍을 찾으면 $k$가 될 수 있는 최소의 양의 정수를 구할 수 있다.

구현은 다음과 같다. 만약 구하는 이산 로그가 존재하지 않을 경우 discrete_log 함수는 $-1$을 반환한다. pow 함수와 phi 함수는 이전 글들에서 정의한 것과 동일하다. (phi 함수의 경우 매개변수의 자료형과 반환형으로 int형 대신 long long형을 사용했으나 나머지는 전부 같다.)

typedef long long LL;
map<LL, LL>M;
LL pow(LL x, LL y, LL p);
LL phi(LL n);
LL discrete_log(LL a, LL p, LL m)
{
    LL v = ceil(sqrt(m)), k = pow(a, phi(m) - 1, m);
    for(int i = 0; i < v; i++)
    {
        if(M.find(p) == M.end())M[s] = i;
        p = p * k % m;
    }
    k = pow(a, v, m);
    p = 1;
    for(int i = 0; i < v; i++)
    {
        if(M.find(p) != M.end())return i * v + M[p];
        p = p * k % m;
    }
    return -1;
}

이 방법을 이용하면 이산 로그를 빠르게 구할 수 있으며 $a$가 $m$의 원시근이 아닌 경우에도 위 식을 만족하는 $k$를 구할 수 있다. 그밖에도 이산 로그를 구하는 다양한 방법이 존재하며, 이에 대한 내용은 참고 링크의 블로그 3에서 볼 수 있다.

 

[참고 링크]

 

순환군

원시근

블로그 1

블로그 2

블로그 3

 

[연습문제]

 

BOJ 4357. 이산 로그 (Platinum I)

Baby-Step Giant-Step으로 이산 로그를 구하면 되는데, 이산 로그가 존재하지 않는 경우도 입력될 수 있으므로 그런 경우를 처리해 주어야 한다. 마지막에 양변의 값이 같은 쌍이 하나도 나오지 않으면 이산 로그가 존재하지 않는다.

 

→ solved.ac tag: discrete_log