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 문제를 효율적으로 계산할..
더보기
Primitive Root
어떤 정수 a가 주어졌을 때, a^n의 형태가 (mod p)의 모든 나머지를 가지고 있다면, 이것을 Primitive Root라고 한다. a = 3, p = 7의 예를 들어보자. 3 ≡ 3 (mod 7) 9 ≡ 2 (mod 7) 27 ≡ 6 (mod 7) 81 ≡ 4 (mod 7) 243 ≡ 5 (mod 7) 729 ≡ 1 (mod 7) 여기서, 1, 2, 3, 4, 5, 6의 나머지를 얻었는데, 이것은 7의 모든 나머지를 가진 것이다. 이와 같은 경우, 3은 mod 7의 Primitive Root이다. 또, Prime Number p는 Φ(p - 1)의 Primitive Root를 가진다. 예를 들어, 2, 6, 7, 8은 mod 11의 Primitive Root이다.
더보기