이산 로그

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

이산 로그(離散 -, discrete logarithm)는 일반 로그와 비슷하게 군론에서 정의된 연산으로, a^x = b를 만족하는 x를 가리킨다.

정의[편집]

이산 로그의 가장 단순한 형태는 Zp*에서 정의하는 것이다. Zp*의 집합은 {1, …, p − 1}이고 소수 p를 법으로 가지는 모듈로 곱셈에 대하여 닫혀있다. 이 군에서 어떤 수의 k 제곱을 구하려면, 그 수를 k번 제곱한 다음 p로 나눈 나머지를 구하면 된다. 이런 연산을 이산 거듭제곱(discrete exponentiation)이라고 한다. 예를 들어, Z7*에서 3의 5제곱을 구하는 경우, 35=243 이고 243을 7로 나눈 나머지가 5이므로 Z7*에서 35=5이다. 이산 로그는 이산 거듭제곱의 역함수이다. 앞의 예제를 사용하여 설명하면, 3k ≡ 5 (mod 7)일 때 이 조건을 만족시키는 가장 작은 kZ7*에서 밑이 3인 5의 이산 로그값이다.

이산 로그의 정의를 일반화하면 다음과 같다. Gn개의 원소를 가진 유한 순환군이라고 하자. 이 군은 곱셈군이라고 가정한다. bG의 생성원이면 G의 모든 원소 x는 임의의 정수 k에 대하여 x = bk의 형태로 쓸 수 있다. 또한 x를 표현하는 모든 원소들은 모듈로 n에 대해 합동이다. 이런 조건에서 다음과 같은 함수를 정의한다.

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

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

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

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

알고리즘[편집]

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

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

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

암호학[편집]

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

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