Computing Discrete Logarithm
discrete logarithm 문제를 효율적으로 해결하는 방법은 알려져 있지 않지만, 간단한 수로 이루어져 있을 경우 쉽게 계산할 수 있다. β ≡ α^x (mod p)가 주어졌다고 하고, x를 구한다고 하자. 먼저, 오일러의 정리를 적용하면, p는 Prime Number이므로, α^(p - 1) ≡ 1 (mod p)이다. 여기서, α^((p - 1) / 2)^2 ≡ ±1 (mod p) 위와 같은 형태를 얻어낼 수 있으며, discrete logarithm의 정의를 살펴보면 p - 1이 α^(p - 1) ≡ 1 (mod p)를 만족하는 가장 적은 지수여야 하기 때문에, α^((p - 1) / 2) ≡ -1 (mod p)가 된다. 이제, β ≡ α^x (mod p)를 알아보면, β^((p - 1) / ..
더보기
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 문제를 효율적으로 계산할..
더보기