폴라드의 p-1 알고리즘?
폴라드의 p-1알고리즘은 폴라드가 1974년 폴라드가 발견한 소인수분해 알고리즘이다. 특수한 유형에서 어떤 수 n-1의 소인수들이 매우 많거나 작은 소인수들이 많은 자연수에 적합하다고 한다.
이름이 p-1인 이유로 주어진 정수 n을 소인수분해 하기 위해 n의 소인수 p를 알아내고자, 페르마의 소정리에서 p-1을 활용하기 때문이다.
원리
pollard's p-1 algorithm은 페르마의 소정리를 이용한다.
n이 p라는 소인수를 가진다고 하자. p와 서로소인 a에 대해서,
페르마의 소정리 $a^{p-1} \equiv 1 \pmod p$가 성립한다.
a를 보통 2로 많이 사용한다.
$a^{p-1} \equiv 1 \pmod p$ 이므로 $a^{k(p-1)} \equiv 1 \pmod p$도 성립한다.
$k(p-1)$을 $E$라고 하자. 즉, $(p-1) | E$ 이다. $a^{E} \equiv 1 \pmod p$.
모듈러의 성질에 의해 $a^E - 1 \equiv 0 \pmod p$이고, $p | a^E -1$이다. 동시에, $p | N $ 이므로
$\gcd(a^E -1 , N) = p$이다.
p를 모르더라도, $(p-1) | E$가 되도록 숫자 E를 적절하게 고르면 p를 알아낼 수 있다.
적절한 E 선택
그러나 알아낼 수 없는 경우가 있는데, 어떤 소인수에 대해서도 $(p-1) \nmid E$일 경우이거나,
N = pq인 두 소수 p, q에 대해서 ${p-1} | E$ 이고 ${q-1} | E$ 일 때이다.
먼저, $(p-1) \nmid E$인 경우에는 $p | a^E -1$이 성립하지 않는다.
그러면 $N$과 $a^E -1$ 도 서로소가 될테고, 값이 1이 나올 것이다.
${p-1} | E$ 이고 ${q-1} | E$ 일 때는 $pq | a^E -1$이고 그러면 $\gcd(a^E -1 , N) = N$일 것이다.
E가 너무 작으면 1이 결과로 나올 것이고, 너무 크면 N이 나오기 때문에 적절한 E 선택이 필요하다.
또한 E에 들어가는 소인수 종류가 너무 적으면 그것도 $(p-1) \nmid E$ 일 것이다.
이를 해결하기 위해서 팩토리얼, 혹은 lcm을 사용한다.
lcm이 팩토리얼에 비해 성능은 더 좋다고 한다.
팩토리얼을 사용할 때는 적절한 수 B를 가지고 $B! = E$를 계산한다.
계산과 구현
E는 매우 크기 때문에, $Q \equiv Q_0 \bmod N$일 때, $\gcd(Q, N) = \gcd(Q_0, N)$임을 이용하여 매번 모듈러를 적용한다.
def gcd(a, b):
while b:
a, b = b, a % b
return a
def pollards_p_1(n, B=10**6):
a = 2
for j in range(2, B+1):
a = pow(a, j, n)
d = gcd(a - 1, n)
if 1 < d < n:
return d
return NoneB는 디폴트로 $10^6$ 이다. 이 코드는 소인수분해라기보다 RSA 문제를 풀기 위해 n = pq인 상황을 가정하고 만들어졌다.
a를 2라고 해두고 a는 반복문을 돌면서 E를 계산해간다. 여기서는 E로 팩토리얼을 적용했다.
적절한 E를 선택하기 위해서 팩토리얼 하나하나 곱해질 때 마다 $\gcd(a^E -1 , N) = p$인 값이 나오는지를 if 문으로 확인한다.
정상적인 값이면 1보다 크고 n보다 작을 것이므로 return 한다.
대응 방안
pollard's p-1 algoritm을 대응하는 방안으로는 p, q 모두 안전 소수를 사용하는 것이다. 둘 중하나라도 안전 소수가 아니라면 하나의 소수를 알고 나눗셈으로 계산 가능하다.
안전 소수인 소피 제르멩 소수를 사용하면 된다.
소피 제르멩 소수는 소수 q에 대해서 p = 2q + 1을 만족하는 소수 p를 말한다.
p-1을 사용하려면 인수로는 적어도 q라는 소수를 포함해야 한다. q도 40자리 이상의 큰 소수라면, 굉장히 찾기가 까다로워 진다.
디레클레 정리와도 관련이 있다.
틀린 부분 있으면 지적해주십시오.
