문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. '''윌리엄스 p+1 소인수분해법'''(Williams' p+1 factorization algorithm)은 큰 자연수를 소인수분해하는 방법으로, 휴 윌리엄스(Hugh Cowie Williams)가 고안하였다. 이 방법은 [[폴라드 p-1 소인수분해법]]에서 파생 및 변형된 방법으로, 소인수를 방식이 서로 유사하다. == 아이디어 == [[폴라드 p-1 소인수분해법]]이 [[페르마의 소정리]]를 이용하여 세운 알고리즘이라면, 이쪽은 [[뤼카 수열]]의 성질을 이용한다. 정해진 상수 <math>P, Q</math>에 대해 <math>V_n(P, Q)</math>는 <math>V_0=2, V_1=P, V_n=PV_{n-1}-QV_{n-2}</math>로 정의된 제2종 뤼카 수열이다. 이 알고리즘에서는 <math>Q=1</math>이라 두고 <math>P</math>를 자유롭게 정해서 수열의 항을 계산한다. 위 점화식을 풀면 <math>V_n=V_n(P, 1)=\alpha^n+\alpha^{-n}, \alpha=\frac{P+\sqrt{D}}{2}, D=P^2-4</math>이다. 한편 페르마의 소정리와 닮은 성질로, <math>p</math>가 홀수 소수일 때 <math>V_{p-\delta} \equiv 2 \pmod p</math>라는 식이 있다. 여기서 <math>\delta=\left(\frac{D}{p} \right)</math>는 [[르장드르 기호]]로, 값은 ±1이다. 참고로 이 관계식은 임의의 자연수 <math>K</math>에 대해 <math>V_{K(p-\delta)} \equiv 2 \pmod p</math>도 성립한다. 만약 알고리즘에서 어떤 큰 자연수 <math>E</math>를 상정했더니 <math>p-\delta \mid E \Leftrightarrow E=K(p-\delta)</math> 조건에 걸려든다면, 위 문단의 합동식에 의해 <math>p \mid V_E-2</math>가 성립한다. 동시에 <math>p</math>가 우리가 찾고자 하던 합성수 <math>N</math>의 소인수라면, <math>p \mid N</math>이므로 <math>p \mid \gcd(V_E-2, N)</math>을 이끌어낼 수 있다. 물론 <math>V_E</math>의 값 자체는 무시무시하게 크기 때문에, 실제 계산에서는 <math>\gcd(V_E-2 \mod N, N)</math>을 목표로, 즉 [[모듈러산술]] 내에서 진행한다. 정리하면 <math>N</math>은 소인수분해를 하려는 입력 받은 값, <math>P, E</math>는 알고리즘에서 지정하는 값, <math>V_E-2</math>는 알고리즘에서 계산할 목표, <math>p</math>는 우리가 알고 싶은 소인수이다. 알고리즘에서는 <math>p</math>의 정체를 모르는 채로 진행하므로 <math>E</math>를 '''충분히 큰 수''', 그 중에서도 약수가 충분히 많은 수로 잡아야 한다. 이 조건에 적합한 값은 어떤 기준값 <math>B</math>를 골라서 <math>\operatorname{lcm}(2, 3, \cdots B)</math>를 셈하는 것이다. 왜 <math>B</math> 이하의 자연수들의 최소공배수가 적합한지는 [[폴라드 p-1 소인수분해법#거듭제곱의 지수 고르기|이 섹션]]을 참고. == 알고리즘 == 소인수분해를 하려는 합성수 <math>N</math>을 입력 받고 아래 과정을 시행한다. * (◆) 2보다 큰 <math>P=V_1</math>의 값을 임의로 지정한다. * (◇) 항 번호를 셈할 기준값 <math>B</math>를 고른다. * 항 번호 <math>\displaystyle E =\operatorname{lcm}(2, 3, \cdots B) =\prod_{\text{primes}\ q \leq B}q^{\lfloor \log_q B \rfloor}</math>를 셈한다. * <math>Q=V_E-2 \mod N</math>을 셈한다. * <math>g=\gcd(Q, N)</math>을 셈한다. * <math>1<g<N</math>이면 여기서 알고리즘이 끝난다. 최대공약수 값이 소수이면 계산을 마치고 <math>g</math>를 소인수로 출력한다. 합성수이면 도출된 값을 다시 소인수분해한다. * <math>g=1</math>이면 <math>B</math>의 값을 올려서 (◇) 단계로 돌아가거나, <math>P</math>의 값을 바꿔서 (◆) 단계로 돌아가거나 "실패"를 출력한다. * <math>g=N</math>이면 <math>B</math>의 값을 내려서 (◇) 단계로 돌아가거나 "실패"를 출력한다. 아무리 <math>B</math>를 올리거나 <math>P</math>를 바꿔도 원하는 소인수를 찾지 못한다면, 알고리즘 자체의 한계에 부딪힌 것이다. 자세한 내용은 아래 '한계점' 문단 참고. === 수열의 특정 항을 셈하는 방법 === 제2종 뤼카 수열에는 항 번호간 성질이 하나 있다. :<math>V_{2n}=V_n^2-2, V_{2n+1}=V_nV_{n+1}-P</math> 이를 달리 쓰자면, <math>(x, y)=(V_n, V_{n+1})</math>이라 할 때, <math>x'=x^2-2, y'=xy-P</math>라 하면 <math>(x', y')=(V_{2n}, V_{2n+1})</math>이다. 또, 반대로 <math>x'=xy-P, y'=y^2-2</math>라 하면 <math>(x', y')=(V_{2n+1}, V_{2n+2})</math>가 된다. 중요한 것은 두 변수는 뤼카 수열의 '''서로 이웃한 항'''이며, <math>y</math>는 <math>x</math>의 바로 다음 항이 되도록 하는 것이다. 또, 각 단계에서 <math>x</math>의 값은 <math>V_n \to V_{2n} \text{ or } V_{2n+1}</math> 두 갈래 길 중 하나를 고를 것이다. 먼저 <math>(x, y)=(V_0, V_1)=(2, P)</math>를 초깃값으로 삼는다. 그 다음 <math>E</math>를 이진법으로 전개하고, 맨 왼쪽의 비트부터 오른쪽으로 읽어나간다. 각 비트가 각 단계가 된다. 이때 비트의 값이… * 0이면 <math>x'=x^2-2 \mod N, y'=xy-P \mod N</math> (ⓐ) * 1이면 <math>x'=xy-P \mod N, y'=y^2-2 \mod N</math> (ⓑ) * <math>(x, y) \leftarrow (x', y')</math> 이렇게 계산과 변수 갱신을 반복하면 <math>x=V_E \mod N</math>에 도달한다. 가령 <math>B=7, V_{420} \mod N</math>을 셈하고 싶다면, 420을 이진법으로 전개한다. 즉 110100100과 같이 써지고, 맨 왼쪽부터 비트를 읽어나가서 ⓐ, ⓑ중 나아갈 길을 택한다. * <math>(x, y)=(V_0, V_1)</math> * 비트 1: ⓑ→ <math>(x, y)=(V_1, V_2)</math> * 비트 1: ⓑ→ <math>(x, y)=(V_3, V_4)</math> * 비트 0: ⓐ→ <math>(x, y)=(V_6, V_7)</math> * 비트 1: ⓑ→ <math>(x, y)=(V_{13}, V_{14})</math> * 비트 0: ⓐ→ <math>(x, y)=(V_{26}, V_{27})</math> * 이렇게 비트를 계속 추적해 나가면 마지막에는 <math>(x, y)=(V_{420}, V_{421})</math>을 얻고, 이때 <math>x</math>의 값이 계산 목표이다. == 적용 예 == <math>N=31910017</math>을 소인수분해하려고 한다. <math>B=20, E=232792560</math>이라 하고 <math>V_E \mod N</math>을 셈한다. 이때 초기 조건은 <math>P=9, (x, y)=(2, 9)</math>이다. 위 문단의 방식대로 항을 계산하면 <math>x \equiv 17535623 \pmod N</math>이 나온다. 최대공약수를 셈하면 <math>\gcd(x-2, N)=4079</math>로 비자명한 약수가 나온다. 또한 주어진 자연수에다 이 값으로 나누면 <math>N=4079 \cdot 7823</math>을 얻고 알고리즘은 성공한다. 이 방법이 통한 것은 <math>4079+1=2^4 \cdot 3 \cdot 5 \cdot 17</math>로, 자잘한 소수들로 나눠지기 때문이다. 구체적으로는 모든 소수의 거듭제곱 항이 <math>B</math>보다 작아서, <math>4080 \mid E</math>라는 조건에 다다를 수 있었다. 한편 <math>D=P^2-4=77</math>에 대해 [[르장드르 기호]] 값은 <math>\delta=\left(\frac{77}{4079}\right)=-1</math>이므로, 위 아이디어에서 언급한 조건식을 가져오면 <math>V_{4080} \equiv 2 \pmod{4079}</math>이다. 나아가 <math>E=4080K</math>이므로 <math>V_E \equiv 2 \pmod{4079}</math>이기에 <math>4079 \mid V_E-2, 4079 \mid \gcd(V_E-2, N)</math> 조건을 만족하게 되고, 이것이 알고리즘이 통한 이유이다. 반면 여인수인 7823의 경우 <math>\left(\frac{77}{7823}\right)=-1</math>이며 <math>7823+1=2^4\cdot 3 \cdot 163</math>이다. 나누어진 각 항 중 가장 큰 값은 163이므로 <math>7824 \nmid E</math>이고, 이에 따라 <math>V_{7824} \equiv 2 \pmod{7823}</math>이지만 <math>V_E \not\equiv 2 \pmod{7823}</math>이 되었다. 그렇기에 <math>\gcd(V_E-2, N)</math>을 셈할 때 소인수는 4079는 추출했지만 7823은 딸려나오지 않게 되고, 이것이 두 소인수의 곱을 분리하게 된 것이다. === 초기 조건이 다르다면 === 만약 <math>P=7</math>이라 놓는다면 계산 결과는 <math>V_E \equiv 31549656 \pmod N</math>이다. 그런데 이 경우 <math>\gcd(V_E-2, N)=1</math>이 나와서 원하는 결과를 얻지 못한다. 그 이유는 <math>D=45, \left(\frac{45}{4079}\right)=1</math>이며 <math>4079-1=2 \cdot 2039</math>이기 때문이다. 가장 큰 항이 <math>B</math>보다 훨씬 크기에, <math>4078 \nmid E</math>이고 이에 따라 <math>V_E \not\equiv 2 \pmod{4079}</math>가 되었다. 여인수 7823도 마찬가지 이유로 합동식을 만족하지 않는다. <math>D=45, \left(\frac{45}{7823}\right)=-1</math>이지만 바로 위 문단에서 살펴보았듯 7824 역시 <math>E</math>의 약수가 되지 못한다. 이처럼 윌리엄스 방식으로 소인수분해를 할 때에는 초깃값 <math>P</math>에 따라 알고리즘의 성공 여부가 달라진다. == 폴라드 p-1 소인수분해법과 비교 == [[폴라드 p-1 소인수분해법]]에서는 페르마의 소정리와 모듈러산술에서의 거듭제곱을 이용하여 소인수를 찾는다. 소인수를 발견할 조건은 <math>p-1 \mid E</math>이다. 한편 본 문서에서 소개한 방법은 <math>p-\delta \mid E</math>의 성립 여부이다. 이때 <math>\delta=\left(\frac{D}{p}\right)</math>는 ±1이므로, 결국에는 <math>p \pm 1 \mid E</math>를 목표로 찾아다니는 셈이 된다. 어떤 소인수 <math>p</math>에 대해 <math>p \pm 1</math>을 소인수분해할 때, 더 자잘한 소수의 거듭제곱들로 쪼개지는 쪽이 더 다루기 쉽다. 이를테면 <math>p=1009</math>일 때, <math>p-1= 2^4 \cdot 3^2 \cdot 7, p+1=2 \cdot 5 \cdot 101</math>이다. 전자는 가장 큰 덩어리가 2의 4제곱, 즉 16이고, 후자는 101이 가장 크다. 이 말은 즉 <math>E=\operatorname{lcm}(2, 3, \cdots B)</math>를 셈할 때 <math>p \pm 1 \mid E</math>가 성립하기 위한 최소 <math>B</math>는 <math>p-1</math>의 경우 16, <math>p+1</math>의 경우 101이다. 만약 <math>B=20</math>으로 둔다면 <math>p-1</math>은 알고리즘이 성공하지만 <math>p+1</math>은 성공하지 못한다. 그런데 사실 <math>p-1</math>을 다루기 쉬운 소인수는 폴라드 p-1 소인수분해법을 쓰는 것이 빠르다. 앞서 알고리즘을 소개할 때 <math>(V_n, V_{n+1})</math>의 다음 항인 <math>(V_{2n}, V_{2n+1}) \text{ or } (V_{2n+1}, V_{2n+2})</math>를 셈할 때에는 두 개 항을 계산해야 한다. 하지만 폴라드의 방법은 밑이 고정된 거듭제곱, 즉 <math>a^E-1 \mod N</math>을 셈하는 것이기에, <math>a^n</math> 다음 항인 <math>a^{2n} \text{ or } a^{2n+1}</math>을 계산하려면 그 값을 제곱하고 필요시 원래 밑을 곱해주면 된다. 즉 계산할 변수가 하나이기에, 같은 <math>B, E</math>라도 윌리엄스의 방법보다 연산량이 절반 가량 적다. 더구나 폴라드의 방법에서는 <math>p \mid N, p-1 \mid E</math>이면 무조건 <math>a^E \equiv 1 \pmod N</math>을 만족하지만, 이쪽은 <math>p-1 \mid E</math>이더라도 절반의 확률로 초깃값 <math>P</math>에 대해 <math>\delta=-1</math>이면 <math>V_{p+1} \equiv 2 \pmod N</math>이 되어서 알고리즘은 수포로 돌아간다. 따라서 윌리엄스의 방법은 보통 폴라드의 방법에서 찾기 매우 어려운 경우, 즉 <math>p+1 \mid E</math>인 상황에 주로 관심을 두고 있으며, 이것이 윌리엄스 '''p+1''' 소인수분해법이라 불리는 이유이다. === 초기 조건을 설정할 때 유의사항 === 초깃값은 반드시 3 이상으로 잡는다. <math>P=2</math>이면 뤼카 수열은 <math>V_n(2, 1): 2, 2, 2, \cdots</math>와 같이 모든 항이 2가 되며, <math>P=1</math>이면 <math>V_n(1, 1): 2, 1, -1, -2, -1, 1, \cdots</math>과 같이 주기가 6인 수열이 된다. 이렇게 되면 <math>p, q \mid N</math>인 서로 다른 두 소인수에 대해 <math>p \mid V_E-2, q \nmid V_E-2</math> 혹은 반대 조건을 이끌어낼 수가 없다. 특정 소인수 <math>p</math>의 입장에서 자기와 바로 이웃한 수인 <math>p \pm 1</math>이 <math>E</math>의 타겟이다. 앞서 언급한 소인수인 4079의 경우, <math>p-1</math>이 타겟이면 <math>E \geq 2039</math>일 때 <math>p-1 \mid E</math>를 만족하지만 <math>p+1</math>이 타겟이면 <math>E \geq 17</math>일 때 <math>p+1 \mid E</math>가 된다. 둘 중 <math>E</math>의 하한선이 낮은 쪽이 소인수를 잡아내기 쉬운 값이다. 그렇기에 윌리엄스의 방법으로 소인수를 찾을 때에는 <math>E</math>가 <math>p \pm 1</math>양쪽에 접근할 수 있도록 설계해야 한다. 폴라드 p-1 소인수분해법에서는 <math>E</math>의 타겟이 <math>a</math>에 관계 없이 <math>p-1</math>로 일정하기에, 이 방법으로 찾아내지 못한 소인수들에 대해서는 <math>p+1</math>이 타겟이 되도록 <math>P, D=P^2-4</math>를 정해야 한다. 즉 <math>\delta(D, p)=\left(\frac{D}{p}\right)=-1</math>을 목표로 한다. 가령 <math>P=3</math>을 가정했다면 <math>D=5</math>이고, <math>p \equiv \pm 2 \pmod 5 \Leftrightarrow \delta(5, p)=-1</math>이면 <math>p+1</math>이 타겟이 된다. 하지만 <math>p \equiv \pm 2 \pmod 5 \Leftrightarrow \delta(5, p)=1</math>이면 타겟은 <math>p-1</math>이므로, 이걸로는 <math>p+1</math>에 접근하지 못한다. 이번에는 <math>(P, D)=(4, 12)</math>를 넣고 다시 시도한다. 이 경우 <math>\delta(12, p)=\delta(3, p)</math>의 부호에 따라 <math>p+1</math> 접근 여부가 달라진다. <math>p \equiv \pm 5 \pmod{12} \Leftrightarrow \delta(3, p)=-1</math>이면 이 단계에서 <math>p+1</math>에 접근 가능하지만, 그렇지 않으면 초깃값을 또 바꿔야 한다. <math>(P, D)=(7, 45)</math>이면 <math>(P, D)=(3, 5)</math>일 때와 알고리즘 중복으로 '의미 없는 시행'이 된다. 모든 홀수 소수에 대해 <math>\delta(45, p)=\delta(5, p)</math>이기 때문이다. 또, <math>(P, D)=(3, 5), (4, 12)</math>를 시도했다면 이 단계에서 <math>p+1</math>에 접근하지 못한 소인수들은 <math>\delta(3, p)=\delta(5, p)=1</math>인 그룹이다. 그러면 자동으로 <math>\delta(15, p)=\delta(60, p)=1</math>이 성립하므로 <math>(P, D)=(8, 60)</math> 역시 시도할 필요가 없다. 중요한 것은 <math>P, D</math>의 값을 달리할 때 <math>\delta(D, p)</math>가 이전 시행들과 독립된 식이 되도록 맞추는 것이다. == 한계점 == 실제로는 <math>p \pm 1</math>두 값 모두 위 방법으로 잡아내지 못하는 소수가 많이 존재하기에, 이 경우 알고리즘이 성공하기 매우 어렵다. 가령 <math>N=pq=3391934713, p=50207, q=67559</math>의 경우 <math>p-1=2 \cdot 13 \cdot 1931, p+1=2^5 \cdot 3 \cdot 523</math>인데 양쪽 모두 큰 소인수를 포함하고 있다. 다른 소인수도 마찬가지: <math>q-1=2 \cdot 17 \cdot 1987, q+1=2^3 \cdot 3 \cdot 5 \cdot 563</math> 이렇게 되면 그나마 최대 소인수가 가장 작은 <math>p+1</math>을 공략하더라도 <math>B \geq 523</math>으로 잡아야 소인수를 잡아낼 수 있다. 특수한 경우가 아닌 이상 보통은 활용도가 높은 [[렌스트라 타원곡선 소인수분해법]]이나 [[이차 체]]를 많이 이용한다. 전자의 경우 특정 소인수를 잡기 위한 타겟을 <math>p \pm 1</math> 말고도 여러 값으로 바꾸어갈 수 있다. == 변칙 알고리즘 == 최적화 방법에 따라 알고리즘 단계나 계산 방식을 적절히 변형할 수 있다. === 항 연산 분리 === <math>E</math>의 값은 기본적으로 최소공배수 연산으로 고르지만, 여기에 2, 3, 5의 거듭제곱을 따로 분리해서 연산 방식을 달리할 수 있다. 이를테면 <math>B=20, E=2^4 \cdot 3^2 \cdot 5 \cdot E', E'=323323</math>이라 할 때, <math>E'</math>은 7 이상의 소인수들의 곱으로만 이루어져 있다. 이때 <math>V_{E'} \mod N</math>을 먼저 셈한 다음 <math>V_E</math>를 이끌어낸다면 연산량을 단축할 수 있다. 그 이유는 위의 "수열의 특정 항을 셈하는 방법"의 알고리즘에 있다. 일반적으로 <math>V_n</math>으로부터 <math>V_{2n} \text{ or } V_{2n+1}</math>을 이끌어내고자 한다면 순서쌍 <math>(V_n, V_{n+1})</math>을 이용해 '''두 항'''을 같이 계산해야 한다. (이때 곱셈 2회를 시행한다) 하지만 2, 3, 5만을 소인수로 가지는 <math>A</math>에 대해 <math>V_n \to V_{An}</math>을 이끌어내려고 한다면, '''항 하나'''로만 연산을 셈하면 된다. * ⓐ <math>V_{2n}=V_n^2-2</math>: 곱셈 1회 시행 * ⓑ <math>V_{3n}=(V_n^2-3)V_n</math>: 곱셈 2회 시행 * ⓒ <math>V_{5n}=[(V_n^2-5)V_n^2+5]V_n</math>: 곱셈 3회 시행 ** <math>v=V_n^2</math>을 먼저 셈하고 <math>V_{5n}=[(v-5)v+5]V_n</math>을 계산하면 곱셈 횟수는 1+2회이다. 일반적으로 다음 항 계산을 시행한다는 것은 <math>E</math>의 비트를 하나 읽는 것과 등가이다. 앞서 든 예시를 들자면 <math>E=1101111000000010000111110000_{(2)}</math>은 28비트이므로 원래 알고리즘을 따르면 <math>V_E</math>에 도달하기까지 곱셈을 총 56회 시행한다. 반면 <math>E'=1001110111011111011_{(2)}</math>은 19비트이고 <math>V_{E'}</math>에 이르기까지 곱셈 횟수는 38회이다. 또, <math>V_{E'} \to V_{5E'}</math> 단계는 위 ⓒ 방법으로 곱셈 3회, <math>V_{5E'} \to V_{45E'}</math> 단계는 ⓑ 방법×2로 곱셈 4회, 마지막으로 <math>V_{45E'} \to V_E</math> 단계는 ⓐ 방법×4로 곱셈 4회를 시행하므로, 모두 합하면 49회이다. <math>E</math> 내에 포함된 작은 소인수들이 많이 들어갈수록 곱셈 횟수를 많이 단축할 수 있다. 같은 방법으로 <math>V_{7n}</math>을 단항 계산으로 전환하면 연산량은 더 단축되지만 소수 배율이 더 커지면 단축 효과는 떨어진다. === 계산 방식 바꾸기 === 앞서 소개한 방법은 제2종 뤼카 수열을 이용했지만, 사실 이는 무리수의 거듭제곱 표현으로 바꿔 쓸 수 있다. <math>V_1</math>이 짝수인 경우, :<math>V_n(2P', 1)=\alpha^n+\alpha^{-n}, \alpha=P'+\sqrt{D}, D=P'^2-1</math> 식에서 기본 알고리즘에서는 <math>V_n</math>을 셈하는 것이었지만 여기서는 <math>\alpha^n</math>을 직접 셈한다. 물론 <math>\alpha \in \mathbb{Q}(\sqrt{D})</math>이면 <math>\alpha^n \in \mathbb{Q}(\sqrt{D})</math>이므로, 실제로는 <math>\alpha^n=H_n+I_n \sqrt{D}</math>에서 <math>(H_n, I_n)</math>을 계산 및 기록한다. 이때 역수는 <math>\alpha^{-n}=H_n-I_n\sqrt{D}</math>이므로 <math>2H_n=V_n</math>이며, 나아가 <math>p</math>가 소수이면 <math>H_{p-\delta} \equiv 1 \pmod p</math>도 성립한다. 아울러 <math>\alpha^{m+n}=\alpha^m\alpha^n</math>을 <math>H_n, I_n</math>에 관한 식으로 바꾸면 <math>(H_{m+n}, I_{m+n})=(H_m, I_m)\cdot (H_n, I_n)=(H_mH_n+DI_mI_n, H_mI_n+I_mH_n)</math>이다. 또, 초깃값은 <math>H_1=P', I_n=1</math>이다. * 항 번호를 두 배로 뛰기: <math>(H_{2n}, I_{2n})=(H_n, I_n)^2=(H_n^2+DI_n^2, 2H_nI_n)=(2H_n^2-1, 2H_nI_n)</math> * 다음 항 셈하기: <math>(H_{n+1}, I_{n+1})=(H_n, I_n)\cdot(P', 1)=(P'H_n+DI_n, P'I_n+H_n)</math> 이렇게 해서 <math>H_E-1 \mod N</math>을 구하고 <math>\gcd(H_E-1, N)</math>으로부터 비자명한 약수를 찾아내면, 알고리즘은 성공한다. 마찬가지로 모든 곱셈 및 덧셈은 <math>\mathbb{Z}/N\mathbb{Z}</math>상에서 이루어진다. === 두 단계 분할 === [[폴라드 p-1 소인수분해법]]과 마찬가지로 알고리즘을 두 단계로 나눌 수 있다. <math>p-\delta=r_1 r_2 \cdots r_k, r_1<r_2<\cdots<r_k</math>가 소수 또는 소수의 거듭제곱들의 곱일 때, <math>B_1 \geq r_{k-1}, B_2 \geq r_k</math>이 되도록 기준치를 설정하고 아래 방법을 따라가면 원하는 약수를 찾을 수 있다. 두 단계 알고리즘에는 여러 방식이 있지만 여기서는 바로 위 문단의 것을 기준으로 서술한다. 1단계까지는 <math>H_E \mod N</math>을 셈하고, 2단계에서는 <math>B_1 < s_j \leq B_2</math>인 모든 소수 <math>s_j</math>에 대해 <math>\prod_{s_j} (H_{Es_j}-1) \mod N</math>을 계산한다. * 기본 알고리즘과 같이 첫째 목표치 <math>B_1</math>을 지정한다. * 이 기준치에 대응하는 항 번호인 <math>E=\prod_{\text{primes }q \leq B_1} q^{\lfloor \log_q B_1 \rfloor}</math>를 셈한다. * 초깃값 <math>H_1=P'</math>을 지정하고 위 기본 알고리즘으로 <math>H_E-1, I_E \mod N</math>을 셈한다. * 여기까지가 1단계이다. 만약 <math>\gcd(H_E-1, N)</math>으로부터 소인수를 찾으면, 여기서 알고리즘을 종료할 수 있다. 약수를 찾지 못했다면 아래 2단계로 이어진다. * <math>(H_E, I_E)^s=(H_{sE}, I_{sE})</math> 식을 이용하여 <math>(H_{2E}, I_{2E}), (H_{4E}, I_{4E}), (H_{6E}, I_{6E}), \cdots \mod N</math>의 값을 메모리에 가급적 많이 적어둔다. * <math>B_1 < s_j \leq B_2</math>내의 소수 또는 홀수 소수의 거듭제곱 목록을 작성하고 이를 오름차순으로 정렬한다. * <math>(H_{s_1E}, I_{s_1E})=(H_E, I_E)^{s_1}</math>을 셈하고 <math>T=H_{s_1E}-1</math>을 저장한다. * <math>d_j=s_{j+1}-s_j\ (j \geq 1)</math>이라 할 때, 메모리에 적어둔 <math>(H_{d_jE}, I_{d_jE})</math>를 불러와서 <math>(H_{s_{j+1}E}, I_{s_{j+1}E})=(H_{s_jE}, I_{s_jE}) \cdot (H_{d_jE}, I_{d_jE})</math>를 셈한 후 <math>T \leftarrow T(H_{s_{j+1}E}-1)</math>와 같이 값을 갱신한다. * 이렇게 모든 <math>s_j</math>에 대해 계산을 반복하고 나면 <math>T</math>가 바로 2단계의 목표이다. <math>\gcd(T, N)</math>으로부터 비자명한 약수를 얻어내면 알고리즘은 성공한다. == 같이 보기 == * [[폴라드 p-1 소인수분해법]] * [[렌스트라 타원곡선 소인수분해법]] {{각주}} {{수론 알고리즘}} [[분류:알고리즘]] 이 문서에서 사용한 틀: 틀:Skin (원본 보기) 틀:각주 (원본 보기) 틀:둘러보기 상자 (원본 보기) 틀:둘러보기 상자/핵심 (원본 보기) 틀:수론 알고리즘 (원본 보기) 틀:틀바 (원본 보기) 윌리엄스 p+1 소인수분해법 문서로 돌아갑니다.