폴라드의 P-1 알고리즘
폴라드의 p − 1 알고리즘 (Pollard's p-1 algorithm)은 1974년 존 폴라드가 발견한 소인수분해 알고리즘이다. 소인수분해에 사용되는 특수한 유형의 알고리즘으로 어떤 수 n-1의 소인수들이 매우 많거나 작은 소인수들이 많이 있는 자연수에만 적합하다.
이 알고리즘은 많이 쓰이지 않으며, 보통 큰 수를 소인수분해할 때에는 타원곡선 방법이나 이차 체 방법을 더 많이 사용한다.
기본 개념
편집n이 어떤 소인수 p를 가지고 있는 합성수라고 하자. 페르마 소정리에 따르면, p와 서로소인 어떤 양의 정수 a, 그리고 모든 양의 정수 K에 대하여 다음의 관계가 성립한다.
만약 어떤 수 x가 n의 약수로 나눴을 때 나머지가 1이라면, gcd(x-1, n)은 그 약수로 나누어떨어진다.
이 알고리즘은 어떤 한계값인 B 미만의 소수들의 거듭제곱수들을 곱하여 이 수를 많은 소인수들을 가지고 있는 매우 큰 p-1의 배수로 만든다. 그 후, 임의의 정수 x와 앞에서 구한 p-1의 배수인 w로 를 계산하면서 gcd(x − 1, n)이 n의 약수가 되는지 확인한다.
여러 소인수들
편집만약 n의 소인수인 p에 대하여 p-1이 여러 작은 소인수들로 나누어떨어지면, 어떤 특정한 값 이후로는 이 알고리즘은 다시 n을 결과로 출력할 수도 있다.
알고리즘 및 실행 시간
편집기본 알고리즘은 다음과 같이 작성할 수 있다.
- 입력: 어떤 합성수 n
- 출력: n의 비자명한 약수 또는 실패
- 어떤 수 B를 고른다.
- 으로 M의 값을 구한다.
- 무작위로 n과 서로소인 수 a를 고른다. 만약 n이 홀수라면, 항상 a를 2로 정해도 된다.
- g = gcd(aM − 1, n)를 이용하여 g의 값을 구한다.
- 만약 1 < g < n 이면 g를 출력한다.
- 만약 g = 1인 경우 더 큰 B를 선택하고 2 단계로 이동하거나 실패를 출력한다.
- 만약 g = n인 경우 더 작은 B를 선택하고 2단계로 이동하거나 실패를 출력한다.
이 알고리즘의 실행 시간은 O(B × log B × log2 n)이다. 1단계에서 정한 B의 값이 클수록 실행 속도가 느려지지만 비자명한 약수를 출력할 가능성이 커진다.
예시
편집n = 299를 소인수분해해 보자.
- B = 5로 하자.
- 이에 따라 M = 22 × 31 × 51이다.
- a = 2로 하자.
- g = gcd (a M - 1, n ) = 13이다.
- 1<13 <299이므로 13을 출력한다.
- 299 / 13 = 23이 소수이므로 299 = 13 × 23으로 완전히 소인수분해된다.