본문 바로가기

Library/Mathematics

Pohlig-Hellman Algorithm

discrete logarithm 문제를 해결하기 위한 알고리즘으로, Pohlig-Hellman 알고리즘이 있다. 이것은 간단히 discrete logarithm 문제를 해결하는 알고리즘을 좀 더 응용한 것인데, 알고리즘은 다음과 같다.


먼저, Prime Number p에서, p - 1은 어떤 Prime Number의 다항식으로 표현될 수 있다. 즉, p - 1 = x0 + x1 * q + x2 * q^2 + ...와 같은 방식으로 전개할 수 있으며, 0 ≤ xi ≤ q - 1이다.

x = x0 + x1 * q + x2 * q^2 + ...,

x((p - 1) / q) = x0 * ((p - 1) / q)) + (p - 1)(x1 + x2 * q + ...)
= x0((p - 1) / q) + (p - 1) * n

이것을 β ≡  α^x (mod p)에 적용해보면,

β^((p - 1) / q) ≡  α^(x * (p - 1) / q) ≡  α^(x0 * (p - 1) / q) * ≡  α^(x * (p - 1))^n (mod p),

∵ α^(x * (p - 1))^n (mod p) ≡ 1 (mod p)
β^((p - 1) / q) ≡  α^(x * (p - 1) / q) ≡  α^(x0 * (p - 1) / q) (mod p)

이제, x0의 값을 알기 위해 β1 ≡ βα^(-x0) ≡ α^(q(x1 + x2 * q + ...) (mod p), 이 결과에 따라 x0을 결정할 수 있게 된다. 이것을 반복적으로 적용하면 연속되는 x1, x2...의 값을 알게 되며, 여기에서 최초의 다항식 x = x0 + x1 * q + x2 * q^2 + ...의 값을 알 수 있게 된다. 예를 들어 보자.


7^x ≡ 12 (mod 41), x를 구하고자 한다면?

41 = 41 - 1 = 2^3 * 5, 다항식 x = x0 + 2 * x1 + 4 * x2 (mod 8), q = 2
∴ β^((p - 1) / q) ≡  12^20 ≡ -1 (mod 41)
∵ 12^40 ≡ 1 (mod 41)

같은 이유로, 7^20 ≡ -1 (mod 41),
β^((p - 1) / q) ≡  α^(x0 * (p - 1) / q) (mod p),
(-1) ≡ (-1)^x0 (mod 41)을 만족하는 x0 = 1


다음으로, β1 ≡ βα^(-x0) ≡ 12 * 7^(-1) ≡ 31 (mod 41),  ∵ 7^(-1) ≡ 6 (mod 41)
∴ β^((p - 1) / q^2) ≡ 31^10 ≡ 1 (mod 41), 이것은 -1이 아닌데, 31은 12나 7과 다른 generator이기 때문이다. 즉, 12나 7은 p - 1이 가장 작은 지수임을 만족하기 위해서 (p - 1) / 2가 -1이 되어야 했지만 31은 그럴 필요가 없다.

∴ β^((p - 1) / q^2) ≡ (α^((p - 1) / q))^x1 (mod 41),
1 ≡ (-1)^x1 (mod 41), 이것을 만족하기 위한 x1 = 0


계속해서, β2 ≡ βα^(-2x1) ≡ 31 * 7^0 ≡ 31 (mod 41),
β2 ^ ((p - 1) / 2^3) ≡ 31^5 ≡ -1 ≡ α^(((p - 1) / 2))^x2 (mod 41), ∵ 31^10 ≡ 1 (mod 41)
∴ x2 = 1
∴ x = 1 + 2 * 0 + 4 * 1 = 5 (mod 8), (최초의 다항식)

β^((p - 1) / 5) ≡ 12^8 ≡ 18 (mod 41)
α^((p - 1) / q) ≡ 7^8 ≡ 37 (mod 41)

β^((p - 1) / q) ≡  α^(x * (p - 1) / q) ≡  α^(k * (p - 1) / q) (mod p)에서 k 값을 결정하는 것이므로,
37^0 ≡ 1, 37^1 ≡ 37, 37^2 ≡ 16, 37^3 ≡ 18, 37^4 ≡ 10 (mod 41)..

따라서, 37^3 ≡ 18 (mod 41)이며, 원하는 x ≡ 3 (mod 5)이다.


마지막으로, 중국식 나머지 정리를 사용하여 x ≡ 5 (mod 8), x ≡ 3 (mod 5)를 만족하는 x 값을 구하면, 이것이 구하고자 하는 x 값이다. 즉, 5로 나누었을 때 3이 남으며, 8로 나누었을 때 5가 남는 수는 13이다. 즉, 7^13 ≡ 12 (mod 41)이다.


그렇다면, Pohlig-Hellman 알고리즘은 실제로 discrete logarithm 문제를 해결하는데 일반적으로 적용할 수 있는 알고리즘인가? 확실히, 이 알고리즘을 사용하면 discrete logarithm을 계산할 수 있지만, p - 1 = q에 대한 다항식으로 나타나는 것에 대해, q가 커질수록(다시 말해 Prime Number p가 커질수록) 계산이 상당히 복잡해진다. 즉, 실용적으로 적용할 수 있는 알고리즘이 아니다.

이것은, discrete logarithm 문제를 해결하기 어렵게 만들려면 p - 1을 매우 큰 Prime Number로 선택하면 된다는 뜻이다. 이처럼 discrete logarithm 문제는 일반적으로 해결하기가 무척 까다롭기 때문에, 암호학에서 중요하게 사용된다.