폴라드의 P-1 알고리즘 문서 원본 보기

{{위키데이터 속성 추적}}
'''폴라드의 ''p'' &#x2212; 1 알고리즘 (Pollard's ''p-1'' algorithm)'''은 1974년 존 폴라드가 발견한 [[소인수분해]] [[알고리즘]]이다. 소인수분해에 사용되는 특수한 유형의 알고리즘으로 어떤 수 n-1의 소인수들이 매우 많거나 작은 소인수들이 많이 있는 [[자연수]]에만 적합하다.

이 알고리즘은 많이 쓰이지 않으며, 보통 큰 수를 [[소인수분해]]할 때에는 타원곡선 방법이나 [[이차 체]] 방법을 더 많이 사용한다.

== 기본 개념 ==
''n''이 어떤 소인수 p를 가지고 있는 합성수라고 하자. [[페르마 소정리]]에 따르면, p와 서로소인 어떤 양의 정수 a, 그리고 모든 양의 정수 K에 대하여 다음의 관계가 성립한다.

: <math>a^{K(p-1)} \equiv 1\pmod{p}</math>

만약 어떤 수 x가 n의 약수로 나눴을 때 나머지가 1이라면, [[최대공약수|gcd]](x-1, n)은 그 약수로 나누어떨어진다.

이 알고리즘은 어떤 한계값인 ''B'' 미만의 소수들의 거듭제곱수들을 곱하여 이 수를 많은 소인수들을 가지고 있는 매우 큰 p-1의 배수로 만든다. 그 후, 임의의 정수 ''x''와 앞에서 구한 p-1의 배수인 w로 <math>x^w \bmod n</math>를 계산하면서 {{개행 금지|gcd(''x'' &minus; 1, ''n'')}}이 n의 약수가 되는지 확인한다.

== 여러 소인수들 ==
만약 n의 소인수인 p에 대하여 p-1이 여러 작은 소인수들로 나누어떨어지면, 어떤 특정한 값 이후로는 이 알고리즘은 다시 n을 결과로 출력할 수도 있다.

== 알고리즘 및 실행 시간 ==
기본 알고리즘은 다음과 같이 작성할 수 있다.

: '''입력:''' 어떤 합성수 n
: '''출력:''' n의 비자명한 약수 또는 <u>실패</u>
:# 어떤 수 ''B''를 고른다.
:#<math>M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }</math>으로 M의 값을 구한다.
:# 무작위로 n<nowiki/>과 서로소인 수 a를 고른다. 만약 n이 홀수라면, 항상 a를 2로 정해도 된다.
:#{{개행 금지|''g'' {{=}} gcd(''a''<sup>''M''</sup> − 1, ''n'')}}를 이용하여 g의 값을 구한다.
:# 만약 {{개행 금지|1 < ''g'' < ''n''}} 이면 ''g''를 출력한다.
:# 만약 {{개행 금지|''g'' {{=}} 1}}인 경우 더 큰 ''B''를 선택하고 2 단계로 이동하거나 <u>실패</u>를 출력한다.
:# 만약 ''g'' = n인 경우 더 작은 ''B''를 선택하고 2단계로 이동하거나 <u>실패</u>를 출력한다.

이 알고리즘의 [[실행 시간 (알고리즘)|실행 시간]]은 {{개행 금지|O(''B'' × log ''B'' × log<sup>2</sup> ''n'')}}이다. 1단계에서 정한 ''B''의 값이 클수록 실행 속도가 느려지지만 비자명한 [[약수]]를 출력할 가능성이 커진다.

=== 예시 ===
''n'' = 299를 소인수분해해 보자.

:#''B'' = 5로 하자.
:# 이에 따라 ''M'' = 2<sup>2</sup> × 3<sup>1</sup> × 5<sup>1</sup>이다.
:# ''a'' = 2로 하자.
:# ''g'' = [[최대공약수|gcd]] (''a'' <sup>''M''</sup> - 1, ''n'' ) = 13이다.
:# 1<13 <299이므로 13을 출력한다.
:# 299 / 13 = 23이 소수이므로 299 = 13 × 23으로 완전히 소인수분해된다.

== 이용 ==
[[GIMPS]]에서는 어떤 [[메르센 수]]의 약수를 구할 때 이 알고리즘을 개선한 방법으로 약수를 구하기도 한다.

{{수론 알고리즘}}

[[분류:소인수 분해 알고리즘]]