본문 바로가기

Library/Mathematics

Discrete Logarithm

어떤 Primve Number p가 있고, 0이 아닌 정수 α, β가 존재한다고 했을 때,

β ≡ α^x (mod p)

여기서, x를 구하는 것을 discrete logarithm 문제라고 한다. 여기서, α^n ≡ 1 (mod p)라고 했을 때, n이 이것을 만족하는 가장 작은 양의 정수라면, 0 ≤ x < n이며, 여기서

x = Lα(β)

이것을 α를 밑으로 가지는 β의 discrete logarithm이라 한다. 자주, α는 모든 β의 α^n (mod p)의 형태로 나타나는 Primitive Root (mod p)에서 선택된다.


discrete logarithm 문제는 일반적으로 해결하기가 매우 어렵다고 알려져 있다. 여기서 어렵다는 말은, discrete logarithm 문제를 효율적으로 계산할 수 있는 알고리즘은 아직까지 알려져 있지 않다는 뜻이다.

α, x가 주여졌다면 α^x (mod p)를 계산하는 것은 쉽지만, 반대로 x = Lα(β)을 계산하는 것은 쉽지 않은데, 이러한 함수를 one-way function이라 한다. f(x)를 구하는 것은 쉽지만, 함수값 y가 주어졌을 때 x를 찾아내는 것은 쉽지 않은 함수이다. discrete logarithm은 대표적인 one-way function이라 할 수 있다.