어떤 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이라 할 수 있다.
β ≡ α^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이라 할 수 있다.