이산 로그

이산 로그(離散--, discrete logarithm)는 일반 로그와 비슷하게 군론에서 정의된 연산으로, $a^{x}=b$를 만족하는 $x$를 가리킨다. 이산 대수(離散對數)라고 부르기도 한다.

정의

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

알고리즘

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

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

이러한 방법에 비교하여 효율적인 알고리즘이 여럿 제안되어 있다. 이들 역시 지수적 복잡도를 가진다.

• 아기걸음 거인걸음
• 폴라드 로 이산 로그 알고리즘
• Pohlig-Hellman 알고리즘
• Index calculus 알고리즘

암호학

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

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