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) / 2) ≡ α^(x * ((p - 1) / 2)) (mod p)이므로, β^((p - 1) / 2) ≡ (-1)^x (mod p)의 결과를 얻게 된다.
즉, β^((p - 1) / 2)의 결과는 x가 짝수인지, 홀수인지에 따라 ±1로 결정된다고 할 수 있다.
예를 들어, 2^x ≡ 9 (mod 11)에서 x를 구하고자 한다면 어떤가?
먼저, β^((p - 1) / 2) ≡ 9^5 ≡ (-1)^x (mod 11)인데, β^(p - 1) ≡ 1 (mod 11)이기 때문에, x는 짝수라는 결론을 얻을 수 있다. 위 식을 만족하는 x 값은 6, 16, 26.. 등이 있으며, discrete logarithm의 정의에서 가장 작은 지수가 x이며, 또 짝수일 때, 6임을 알 수 있다.
이러한 방법은 어디까지나 주어진 수들이 쉽게 계산이 가능할 때 적용 가능한 방법이며, 수가 복잡해지면 위의 방법을 단순하게 적용하여 원하는 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) / 2) ≡ α^(x * ((p - 1) / 2)) (mod p)이므로, β^((p - 1) / 2) ≡ (-1)^x (mod p)의 결과를 얻게 된다.
즉, β^((p - 1) / 2)의 결과는 x가 짝수인지, 홀수인지에 따라 ±1로 결정된다고 할 수 있다.
예를 들어, 2^x ≡ 9 (mod 11)에서 x를 구하고자 한다면 어떤가?
먼저, β^((p - 1) / 2) ≡ 9^5 ≡ (-1)^x (mod 11)인데, β^(p - 1) ≡ 1 (mod 11)이기 때문에, x는 짝수라는 결론을 얻을 수 있다. 위 식을 만족하는 x 값은 6, 16, 26.. 등이 있으며, discrete logarithm의 정의에서 가장 작은 지수가 x이며, 또 짝수일 때, 6임을 알 수 있다.
이러한 방법은 어디까지나 주어진 수들이 쉽게 계산이 가능할 때 적용 가능한 방법이며, 수가 복잡해지면 위의 방법을 단순하게 적용하여 원하는 x 값을 구할 수 없다.