이산 로그 문서 원본 보기

{{위키데이터 속성 추적}}
'''이산 로그'''(離散--, discrete logarithm)는 일반 [[로그]]와 비슷하게 [[군 (수학)|군론]]에서 정의된 연산으로, <math>a^x = b</math>를 만족하는 <math>x</math>를 가리킨다. '''이산 대수'''(離散對數)라고 부르기도 한다.

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

:<math>\log_b:\  G\ \rightarrow\ \mathbf{Z}_n</math>

여기서 '''Z'''<sub>''n''</sub>은 정수 ''n''을 법으로 가지는 [[환 (수학)|환]]이고 ''x''에는 모듈로 ''n''에 대한 congruence class를 할당한다. 이와 같은 [[군 동형사상]]을 밑이 ''b''인 이산 로그라고 부른다.

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

:<math>\log_c (x) = \log_c(b) \cdot \log_b(x).</math>

== 알고리즘 ==
이산 로그를 효율적으로 계산하는 알고리즘은 2012년 현재 알려져 있지 않다.

가장 단순한 알고리즘으로는 <math>a^x = b</math>에서 <math>x</math>를 0부터 시작하여 하나씩 증가시키는 것이 있으며, 이 알고리즘의 시간 복잡도는 군의 크기에 비례하며, 따라서 군의 크기의 자릿수에는 지수적인 복잡도를 가진다.

이러한 방법에 비교하여 효율적인 알고리즘이 여럿 제안되어 있다. 이들 역시 지수적 복잡도를 가진다.
* [[아기걸음 거인걸음]]
* [[폴라드 로 이산 로그 알고리즘]]
* [[Pohlig-Hellman 알고리즘]]
* [[Index calculus 알고리즘]]

== 암호학 ==

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

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

{{공개 열쇠 암호}}

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