폴라드의 P-1 알고리즘

폴라드의 p − 1 알고리즘 (Pollard's p-1 algorithm)은 1974년 존 폴라드가 발견한 소인수분해 알고리즘이다. 소인수분해에 사용되는 특수한 유형의 알고리즘으로 어떤 수 n-1의 소인수들이 매우 많거나 작은 소인수들이 많이 있는 자연수에만 적합하다.

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

기본 개념

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

${\displaystyle a^{K(p-1)}\equiv 1{\pmod {p}}}$

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

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

여러 소인수들

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

알고리즘 및 실행 시간

기본 알고리즘은 다음과 같이 작성할 수 있다.

입력: 어떤 합성수 n

출력: n의 비자명한 약수 또는 실패

1. 어떤 수 B를 고른다.
2. ${\displaystyle M=\prod _{{\text{primes}}~q\leq B}q^{\lfloor \log _{q}{B}\rfloor }}$으로 M의 값을 구한다.
3. 무작위로 n과 서로소인 수 a를 고른다. 만약 n이 홀수라면, 항상 a를 2로 정해도 된다.
4. g = gcd(a^M − 1, n)를 이용하여 g의 값을 구한다.
5. 만약 1 < g < n 이면 g를 출력한다.
6. 만약 g = 1인 경우 더 큰 B를 선택하고 2 단계로 이동하거나 실패를 출력한다.
7. 만약 g = n인 경우 더 작은 B를 선택하고 2단계로 이동하거나 실패를 출력한다.

이 알고리즘의 실행 시간은 O(B × log B × log² n)이다. 1단계에서 정한 B의 값이 클수록 실행 속도가 느려지지만 비자명한 약수를 출력할 가능성이 커진다.

예시

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

1. B = 5로 하자.
2. 이에 따라 M = 2² × 3¹ × 5¹이다.
3. a = 2로 하자.
4. g = gcd (a ^M - 1, n ) = 13이다.
5. 1<13 <299이므로 13을 출력한다.
6. 299 / 13 = 23이 소수이므로 299 = 13 × 23으로 완전히 소인수분해된다.

이용

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