이산 로그

수학과 컴퓨터 과학에서, **이산 로그**(離散log, )는 어떤 유한 순환군 위에서 정의되는, 해석학적 로그와 유사한 연산이다.

크기가 n인 유한 순환군 G와 그 생성 원소 g가 주어졌을 때, 임의의 군 원소 h는 h=g^k 꼴로 나타낼 수 있다. 이러한 정수 k는 법 n에 대한 합동 아래 유일하므로, 항상 k\in\{0,1,2,\dots,n-1\}로 놓을 수 있다. 이 경우, k를 h의 밑 g에 대한 이산 로그라고 한다.

이산 로그를 나타내는 기호는 통일되어 있지 않다. 해석학의 로그와 같은 기호
:\log_gh
가 가장 흔하다.

**이산 로그 문제**(離散log問題, , 약자 DLP)는 이산 로그를 구하는 알고리즘을 찾는 문제다. 다양한 일반적(, 대략, 모든 군에 통용되는) 지수 시간 알고리즘이 알려져 있으며, 또한 모든 일반적 이산 로그 알고리즘은 항상 지수 시간 이상이다. 그러나 “일반적” 조건을 제거해도 참인지는 알려져 있지 않다.

군의 원소의 차수는 이산 로그의 특수한 경우이다. 군의 원소의 차수는 이 원소를 밑으로 하는, 군의 항등원의 이산 로그와 같다. (물론, 값을 양의 정수로 제한하여야 한다.) 하지만 차수의 경우, 모든 일반적 이산 로그 알고리즘보다 효율적인 일반적인 차수 알고리즘이 알려져 있다.

## 정의
### 이산 로그
다음 데이터가 주어졌다고 하자.
* 크기가 n인 유한 순환군 G
* 생성 원소 g\in G
그렇다면, 임의의 원소 h\in G에 대하여, h=g^k인 정수 k가 존재하며, 또한 이러한 정수들은 서로 법 n에 대하여 합동이다. 이에 따라, 함수
:\log_g\colon G\to\mathbb Z/n
를 정의할 수 있다. 이는 아벨 군의 동형 사상이다. 이를 밑 g에 대한 **이산 로그**라고 한다. 사실,
:g\mapsto\log_g
는 G의 생성 원소들과 동형 사상 G\to\mathbb Z/n들 사이의 일대일 대응이다.

### 벡터 이산 로그
보다 일반적으로, 다음 데이터가 주어졌다고 하자.
* 크기가 n인 유한 다순환군 G
* 유한 개의 군 원소 g_1,\dots,g_r\in G. 또한, 이들은 다음 조건을 만족시킨다.
** 모든 G_i/G_{i-1}이 크기가 n_i이며 g_iG_{i-1}을 생성 원소로 하는 순환군인, G의 부분 정규 부분군들의 열 1=G_0\vartriangleleft G_1\vartriangleleft\cdots\vartriangleleft G_r=G가 존재한다.
그렇다면, 임의의 원소 h\in G에 대하여, h=g_1^{k_1}\cdots g_r^{k_r}인 정수 r조 (k_1,\dots,k_r)가 존재하며, 이러한 정수 r조들은 서로 성분별로 법 n_i에 대하여 합동이다. 즉, 함수
:\log_{g_1,\dots,g_r}\colon G\to\mathbb Z/n_1\times\cdots\times\mathbb Z/n_r
를 정의할 수 있다. 이는 전단사 함수이며, 만약 G가 아벨 군이라면 이는 아벨 군의 동형 사상이다. 이를 밑 g_1,\dots,g_r에 대한 **벡터 이산 로그**()라고 한다.

## 소수 크기 유한체의 곱셈군의 예
이산 로그의 가장 단순한 형태는 **Z***p**에서 정의하는 것이다. **Z***p**의 집합은 {1,&nbsp;…,&nbsp;*p*&nbsp;−&nbsp;1}이고 소수 *p*를 법으로 가지는 모듈로 곱셈에 대하여 닫혀있다. 이 군에서 어떤 수의 *k* 제곱을 구하려면, 그 수를 *k*번 제곱한 다음 *p*로 나눈 나머지를 구하면 된다. 이런 연산을 **이산 거듭제곱**(discrete exponentiation)이라고 한다. 예를 들어, **Z**7*에서 3의 5제곱을 구하는 경우, 35=243 이고 243을 7로 나눈 나머지가 5이므로 **Z***7**에서 35=5이다. 이산 로그는 이산 거듭제곱의 역함수이다. 앞의 예제를 사용하여 설명하면, 3k ≡ 5 (mod 7)일 때 이 조건을 만족시키는 가장 작은 *k*가 **Z***7**에서 밑이 3인 5의 이산 로그값이다.
이산로그문제(discrete logarithm problem)라고도 한다.
이산 로그의 정의를 일반화하면 다음과 같다. *G*가 *n*개의 원소를 가진 유한 순환군이라고 하자. 이 군은 곱셈군이라고 가정한다. *b*가 *G*의 생성원(primitive root, primitive element)이면 *G*의 모든 원소 *x*는 임의의 정수 *k*에 대하여 *x*&nbsp;=&nbsp;*b**k*의 형태로 쓸 수 있다. 또한 *x*를 표현하는 모든 원소들은 모듈로 *n*에 대해 합동이다. 이런 조건에서 다음과 같은 함수를 정의한다.

:\log_b:\  G\ \rightarrow\ \mathbf{Z}_n

여기서 **Z***n*은 정수 *n*을 법으로 가지는 환이고 *x*에는 모듈로 *n*에 대한 congruence class를 할당한다. 이와 같은 군 동형사상을 밑이 *b*인 이산 로그라고 부른다.

로그 함수의 밑변환은 이산 로그에서도 그대로 적용된다. *c*가 *G*의 또다른 생성원이면, 다음 식이 성립한다.

:\log_c (x) = \log_c(b) \cdot \log_b(x).

## 알고리즘
이산 로그 \log_gh를 계산하는 다양한 알고리즘 및 확률적 알고리즘이 존재한다.

이들에 대한 복잡도 분석은 일반적 군 알고리즘()의 개념을 사용하여 기술한다. 대략, 일반적 군 알고리즘은 모든 유한군 위에 적용할 수 있어야 하며, 그 복잡도는 군 연산의 시간 복잡도와 군 원소의 공간 복잡도가 1이라고 가정한 채 센다.

가장 단순한 알고리즘으로는 g^k=h인지 k를 0부터 시작하여 하나씩 증가시켜 가며 확인하는 것이 있다. 이 알고리즘의 시간 복잡도는 군의 크기에 비례하며, 따라서 군의 크기의 자릿수에는 지수적인 복잡도를 가진다. 이러한 방법에 비교하여 효율적인 알고리즘이 여럿 제안되어 있다. 이들 역시 지수 시간 알고리즘이다.
* 아기걸음 거인걸음
* 폴라드 로 이산 로그 알고리즘
* 폴리그-헬먼 알고리즘
* 지표 알고리즘

이산 로그를 효율적으로 계산하는 알고리즘은 2025년 현재 알려져 있지 않다. 일반적 군 알고리즘의 경우, 이산 로그 알고리즘의 복잡도의 타이트한 하계가 알려져 있다.

### 일반적 군 알고리즘
대략, (결정론적) 일반적 군 알고리즘() \mathcal A(\vec g,\vec n)은 다음과 같은 데이터를 입력으로 받는다.
* 어떤 유한군 G의 유한 개의 원소 \vec g\in G^* ((-)^*는 클레이니 스타)
* 유한 개의 정수 \vec n\in\mathbb Z^*
또한, 군 G에 대한 접근은 다음과 같은 군 연산을 통해서만 허용된다.
* 항등원 1_G\in G의 출력
* 두 군 원소 g,h\in G가 주어졌을 때, 곱 gh의 출력
* 군 원소 g\in G가 주어졌을 때, 역원 g^{-1}의 출력
확률적 일반적 군 알고리즘() \mathcal A(G,\vec g,\vec n)의 경우, 다음과 같은 ‘군 연산’이 추가로 허용된다.
* 이산 균등 분포를 따르는 무작위 군 원소 g\in G의 출력
일반적 군 알고리즘과 확률적 일반적 군 알고리즘의 시간 복잡도는 군 연산을 사용하는 횟수이며, 공간 복잡도는 동시에 저장하는 군 원소의 개수이다. 특정 군 위에서의 실제 복잡도를 얻으려면 군 연산 횟수에 군 연산의 실제 복잡도를 곱하고, 군 원소의 개수에 군 원소의 실제 복잡도를 곱해야 한다. 이 정의는 수론적 연산(예를 들어, 주어진 정수의 소인수 분해)의 복잡도를 고려하지 않는다. 하지만 여기서 논의하는 모든 일반적 군 알고리즘의 경우, 수론적 연산의 복잡도를 적어도 군 연산 횟수의 상수배를 점근적 하계로 하도록 둘 수 있다.

### 이산 로그를 계산하는 일반적 군 알고리즘
일반적 군 함수() f는 다음과 같은 데이터로 구성된다.
* 모든 유한군 G에 대하여, 부분 정의 함수 f_G\colon G^*\times\mathbb Z^*\to G^*\times\mathbb Z^*
이는 다음 조건을 만족시켜야 한다.
* 임의의 유한군 동형 사상 \phi\colon G\to H 및 (\vec g,\vec n)\in G^*\times\mathbb Z^*에 대하여, f_H(\phi^*(\vec g),\vec n)=(\phi^*\times\operatorname{id})(f_G(\vec g,\vec n))이거나, 둘 모두 정의되지 않는다.
만약 다음 조건이 성립한다면, (결정론적) 일반적 군 알고리즘 \mathcal A(\vec g,\vec n)이 일반적 군 함수 f를 계산한다고 한다.
* 임의의 유한군 G 및 (\vec g,\vec n)\in G^*\times\mathbb Z^*에 대하여, \mathcal A(\vec g,\vec n)=f_G(\vec g,\vec n)이거나, 둘 모두 정의되지 않는다.
확률적 일반적 군 알고리즘 \mathcal A(\vec g,\vec n)이 입력 (\vec g_0,\vec n_0)\in G_0^*\times\mathbb Z^*에서 일반적 군 함수 f를 계산할 확률은 \mathcal A(\vec g_0,\vec n_0)을 확률 변수로 여겼을 때, \mathcal A(\vec g_0,\vec n_0)=f_{G_0}(\vec g_0,\vec n_0)이거나 둘 다 정의되지 않을 확률이다.

이산 로그는 유한군의 두 원소의 순서쌍을 정수로 대응시키는 부분 정의 함수
:\log_G\colon G\times G\to\mathbb Z
들로 구성된 일반적 군 함수로 여길 수 있다.

이산 로그 \log_gh를 계산하는 일반적 군 알고리즘을 생각하자. 크기가 n인 유한 순환군 위의 이산 로그를 계산하는 일반적 군 알고리즘의 시간 복잡도는 항상 \Omega(\sqrt{\operatorname{gpf}(n)})이다. 여기서 \operatorname{gpf}(n)은 n의 최대 소인수이다.

일반적 군 알고리즘의 경우, 차수는 이산 로그보다 빠르게 계산할 수 있다. 예를 들어, 서덜랜드 소수계승걸음 알고리즘의 시간 복잡도는 o(\sqrt n)이므로, 이를 사용할 수 있다. 따라서, g의 차수 n을 미리 아는지 여부는 이산 로그를 계산하는 일반적 군 알고리즘의 시간 복잡도에 영향을 미치지 않는다.

### 선형 찾기
가장 단순하지만 비효율적인 방법은 h와 같을 때까지
:g,g^2,\dots,g^{n-1}
를 계산하는 것이다.

선형 찾기의 실행 시간은 최대 n, 평균 n/2이다. (따라서 n의 자릿수에 대해서는 지수 시간이다.) 또한, 선형 찾기의 공간 복잡도는 O(1)이다. (즉, 상수 공간이다.)

선형 찾기는 n을 몰라도 유효하다.

### 아기걸음 거인걸음

아기걸음 거인걸음의 아이디어는 rs>n인 두 정수 r, s를 고른 뒤, 먼저 “아기걸음”
:1,g,g^2,\dots,g^{r-1}
을 계산하고 아기걸음과 겹칠 때까지 “거인걸음”
:h,hg^{-r},hg^{-2r},\dots,hg^{-(s-1)r}
을 계산하는 것이다. 이는 나머지 정리를 원리로 한다.

최대 실행 시간은 r+s, 최대 사용 공간은 r이므로, 만약 r\approx s\approx\sqrt n인 경우 시간·공간 복잡도는 O(\sqrt n)이다. s를 늘려 실행 시간을 늘리는 대신, r를 줄여 공간을 절약할 수 있다. 하지만 시간 복잡도와 공간 복잡도의 곱은 항상 \Omega(n)이다.

만약 n을 모르는 경우, 차례로 n=2,2^2,2^3,\dots를 가정한 채 아기걸음 거인걸음을 반복하여도 같은 복잡도를 얻는다.

### 폴리그-헬먼 알고리즘

폴리그-헬먼 알고리즘은 이산 로그 문제를 재귀적으로 크기가 소수인 순환군 위의 이산 로그 문제로 귀결시킨다. 구체적으로, n=n_1n_2인 서로소 양의 정수 n_1, n_2를 고르자. 또한, 정수 n_1^{-1}가 n_1의 \mathbb Z/n_2에서의 곱셈 역원이며, 정수 n_2^{-1}가 n_2의 \mathbb Z/n_1에서의 곱셈 역원이라고 하자. 그렇다면,
:\log_gh\equiv n_2n_2^{-1}\log_{g^{n_2}}h^{n_2}+n_1n_1^{-1}\log_{g^{n_1}}h^{n_1}\pmod n
이다. 이는 이산 로그 문제를 크기가 소수의 거듭제곱인 순환군 위의 이산 로그 문제로 귀결시킨다. 이제 n=p^k라고 하자. 그렇다면,
:\log_gh\equiv \log_{g^{p^{\lfloor k/2\rfloor}}}h^{\lfloor k/2\rfloor}+p^{\lceil k/2\rceil}\log_{g^{p^{\lceil k/2\rceil}}}(h-g^{\log_{g^{p^{\lfloor k/2\rfloor}}}h^{\lfloor k/2\rfloor}})\pmod{p^k}
이다. 이는 이산 로그 문제를 크기가 소수인 순환군 위의 이산 로그 문제로 귀결시킨다. 이 경우는 다시 아기걸음 거인걸음이나 폴라드 로 이산 로그 알고리즘 등을 사용한다.

아기걸음 거인걸음 또는 폴라드 로 이산 로그 알고리즘을 사용하는 경우, 폴리그-헬먼 알고리즘의 시간 복잡도는
:O(\log n(\log\log n+\sqrt{\operatorname{gpf}(n)}))
이다. 공간 복잡도는 아기걸음 거인걸음을 사용하는 경우 O(\sqrt{\operatorname{gpf}(n)}), 폴라드 로 이산 로그 알고리즘을 사용하는 경우 O(1)이다.

## 암호학
암호학에서는 이산 로그의 효율적 알고리즘이 존재하지 않지만, 그 반대 방향인 거듭제곱 연산은 간단히 계산할 수 있다는 일방향 함수의 아이디어를 RSA에서와 마찬가지로 채용하여 이용한 것이다.
디피-헬만 키 교환에서는 비밀 숫자의 거듭제곱을 이용한 정보를 상대방에게 전송하며, 만약 이산 로그 문제를 계산할 수 있다면 원래 비밀 숫자를 알아낼 수 있기 때문에 이산 로그의 비효율성이 보안성에 중요한 역할을 한다. 엘가말 암호와 전자 서명 알고리즘 등의 암호 체계에서도 비슷한 방법을 사용한다.

타원 곡선 암호에서는 유한체에서 정의된 타원 곡선의 순환 부분군의 이산 로그 문제를 사용한다.

## 참고 문헌


분류:군론
분류:암호학
분류:로그
분류:이항연산
분류:컴퓨터 과학의 미해결 문제
분류:유한체
분류:모듈러 산술