윌리엄스 p+1 소인수분해법

윌리엄스 p+1 소인수분해법(Williams' p+1 factorization algorithm)은 큰 자연수를 소인수분해하는 방법으로, 휴 윌리엄스(Hugh Cowie Williams)가 고안하였다. 이 방법은 폴라드 p-1 소인수분해법에서 파생 및 변형된 방법으로, 소인수를 방식이 서로 유사하다.

아이디어

폴라드 p-1 소인수분해법이 페르마의 소정리를 이용하여 세운 알고리즘이라면, 이쪽은 뤼카 수열의 성질을 이용한다.

정해진 상수 $P,Q$에 대해 $V_{n}(P,Q)$는 $V_{0}=2,V_{1}=P,V_{n}=PV_{n-1}-QV_{n-2}$로 정의된 제2종 뤼카 수열이다. 이 알고리즘에서는 $Q=1$이라 두고 $P$를 자유롭게 정해서 수열의 항을 계산한다.

위 점화식을 풀면 $V_{n}=V_{n}(P,1)=\alpha ^{n}+\alpha ^{-n},\alpha ={\frac {P+{\sqrt {D}}}{2}},D=P^{2}-4$이다. 한편 페르마의 소정리와 닮은 성질로, $p$가 홀수 소수일 때 $V_{p-\delta }\equiv 2{\pmod {p}}$라는 식이 있다. 여기서 $\delta =\left({\frac {D}{p}}\right)$는 르장드르 기호로, 값은 ±1이다. 참고로 이 관계식은 임의의 자연수 $K$에 대해 $V_{K(p-\delta )}\equiv 2{\pmod {p}}$도 성립한다.

만약 알고리즘에서 어떤 큰 자연수 $E$를 상정했더니 $p-\delta \mid E\Leftrightarrow E=K(p-\delta )$ 조건에 걸려든다면, 위 문단의 합동식에 의해 $p\mid V_{E}-2$가 성립한다. 동시에 $p$가 우리가 찾고자 하던 합성수 $N$의 소인수라면, $p\mid N$이므로 $p\mid \gcd(V_{E}-2,N)$을 이끌어낼 수 있다. 물론 $V_{E}$의 값 자체는 무시무시하게 크기 때문에, 실제 계산에서는 $\gcd(V_{E}-2\mod N,N)$을 목표로, 즉 모듈러산술 내에서 진행한다.

정리하면 $N$은 소인수분해를 하려는 입력 받은 값, $P,E$는 알고리즘에서 지정하는 값, $V_{E}-2$는 알고리즘에서 계산할 목표, $p$는 우리가 알고 싶은 소인수이다. 알고리즘에서는 $p$의 정체를 모르는 채로 진행하므로 $E$를 충분히 큰 수, 그 중에서도 약수가 충분히 많은 수로 잡아야 한다. 이 조건에 적합한 값은 어떤 기준값 $B$를 골라서 $\operatorname {lcm} (2,3,\cdots B)$를 셈하는 것이다. 왜 $B$ 이하의 자연수들의 최소공배수가 적합한지는 이 섹션을 참고.

알고리즘

소인수분해를 하려는 합성수 $N$을 입력 받고 아래 과정을 시행한다.

• (◆) 2보다 큰 $P=V_{1}$의 값을 임의로 지정한다.
• (◇) 항 번호를 셈할 기준값 $B$를 고른다.
• 항 번호 $\displaystyle E=\operatorname {lcm} (2,3,\cdots B)=\prod _{{\text{primes}}\ q\leq B}q^{\lfloor \log _{q}B\rfloor }$를 셈한다.
• $Q=V_{E}-2\mod N$을 셈한다.
• $g=\gcd(Q,N)$을 셈한다.
• $1<g<N$이면 여기서 알고리즘이 끝난다. 최대공약수 값이 소수이면 계산을 마치고 $g$를 소인수로 출력한다. 합성수이면 도출된 값을 다시 소인수분해한다.
• $g=1$이면 $B$의 값을 올려서 (◇) 단계로 돌아가거나, $P$의 값을 바꿔서 (◆) 단계로 돌아가거나 "실패"를 출력한다.
• $g=N$이면 $B$의 값을 내려서 (◇) 단계로 돌아가거나 "실패"를 출력한다.

아무리 $B$를 올리거나 $P$를 바꿔도 원하는 소인수를 찾지 못한다면, 알고리즘 자체의 한계에 부딪힌 것이다. 자세한 내용은 아래 '한계점' 문단 참고.

수열의 특정 항을 셈하는 방법

제2종 뤼카 수열에는 항 번호간 성질이 하나 있다.

$V_{2n}=V_{n}^{2}-2,V_{2n+1}=V_{n}V_{n+1}-P$

이를 달리 쓰자면, $(x,y)=(V_{n},V_{n+1})$이라 할 때, $x'=x^{2}-2,y'=xy-P$라 하면 $(x',y')=(V_{2n},V_{2n+1})$이다. 또, 반대로 $x'=xy-P,y'=y^{2}-2$라 하면 $(x',y')=(V_{2n+1},V_{2n+2})$가 된다. 중요한 것은 두 변수는 뤼카 수열의 서로 이웃한 항이며, $y$는 $x$의 바로 다음 항이 되도록 하는 것이다. 또, 각 단계에서 $x$의 값은 $V_{n}\to V_{2n}{\text{ or }}V_{2n+1}$ 두 갈래 길 중 하나를 고를 것이다.

먼저 $(x,y)=(V_{0},V_{1})=(2,P)$를 초깃값으로 삼는다. 그 다음 $E$를 이진법으로 전개하고, 맨 왼쪽의 비트부터 오른쪽으로 읽어나간다. 각 비트가 각 단계가 된다. 이때 비트의 값이…

• 0이면 $x'=x^{2}-2\mod N,y'=xy-P\mod N$ (ⓐ)
• 1이면 $x'=xy-P\mod N,y'=y^{2}-2\mod N$ (ⓑ)
• $(x,y)\leftarrow (x',y')$

이렇게 계산과 변수 갱신을 반복하면 $x=V_{E}\mod N$에 도달한다.

가령 $B=7,V_{420}\mod N$을 셈하고 싶다면, 420을 이진법으로 전개한다. 즉 110100100과 같이 써지고, 맨 왼쪽부터 비트를 읽어나가서 ⓐ, ⓑ중 나아갈 길을 택한다.

• $(x,y)=(V_{0},V_{1})$
• 비트 1: ⓑ→ $(x,y)=(V_{1},V_{2})$
• 비트 1: ⓑ→ $(x,y)=(V_{3},V_{4})$
• 비트 0: ⓐ→ $(x,y)=(V_{6},V_{7})$
• 비트 1: ⓑ→ $(x,y)=(V_{13},V_{14})$
• 비트 0: ⓐ→ $(x,y)=(V_{26},V_{27})$
• 이렇게 비트를 계속 추적해 나가면 마지막에는 $(x,y)=(V_{420},V_{421})$을 얻고, 이때 $x$의 값이 계산 목표이다.

적용 예

$N=31910017$을 소인수분해하려고 한다.

$B=20,E=232792560$이라 하고 $V_{E}\mod N$을 셈한다. 이때 초기 조건은 $P=9,(x,y)=(2,9)$이다.

위 문단의 방식대로 항을 계산하면 $x\equiv 17535623{\pmod {N}}$이 나온다. 최대공약수를 셈하면 $\gcd(x-2,N)=4079$로 비자명한 약수가 나온다. 또한 주어진 자연수에다 이 값으로 나누면 $N=4079\cdot 7823$을 얻고 알고리즘은 성공한다.

이 방법이 통한 것은 $4079+1=2^{4}\cdot 3\cdot 5\cdot 17$로, 자잘한 소수들로 나눠지기 때문이다. 구체적으로는 모든 소수의 거듭제곱 항이 $B$보다 작아서, $4080\mid E$라는 조건에 다다를 수 있었다.

한편 $D=P^{2}-4=77$에 대해 르장드르 기호 값은 $\delta =\left({\frac {77}{4079}}\right)=-1$이므로, 위 아이디어에서 언급한 조건식을 가져오면 $V_{4080}\equiv 2{\pmod {4079}}$이다. 나아가 $E=4080K$이므로 $V_{E}\equiv 2{\pmod {4079}}$이기에 $4079\mid V_{E}-2,4079\mid \gcd(V_{E}-2,N)$ 조건을 만족하게 되고, 이것이 알고리즘이 통한 이유이다.

반면 여인수인 7823의 경우 $\left({\frac {77}{7823}}\right)=-1$이며 $7823+1=2^{4}\cdot 3\cdot 163$이다. 나누어진 각 항 중 가장 큰 값은 163이므로 $7824\nmid E$이고, 이에 따라 $V_{7824}\equiv 2{\pmod {7823}}$이지만 $V_{E}\not \equiv 2{\pmod {7823}}$이 되었다. 그렇기에 $\gcd(V_{E}-2,N)$을 셈할 때 소인수는 4079는 추출했지만 7823은 딸려나오지 않게 되고, 이것이 두 소인수의 곱을 분리하게 된 것이다.

초기 조건이 다르다면

만약 $P=7$이라 놓는다면 계산 결과는 $V_{E}\equiv 31549656{\pmod {N}}$이다. 그런데 이 경우 $\gcd(V_{E}-2,N)=1$이 나와서 원하는 결과를 얻지 못한다.

그 이유는 $D=45,\left({\frac {45}{4079}}\right)=1$이며 $4079-1=2\cdot 2039$이기 때문이다. 가장 큰 항이 $B$보다 훨씬 크기에, $4078\nmid E$이고 이에 따라 $V_{E}\not \equiv 2{\pmod {4079}}$가 되었다. 여인수 7823도 마찬가지 이유로 합동식을 만족하지 않는다. $D=45,\left({\frac {45}{7823}}\right)=-1$이지만 바로 위 문단에서 살펴보았듯 7824 역시 $E$의 약수가 되지 못한다.

이처럼 윌리엄스 방식으로 소인수분해를 할 때에는 초깃값 $P$에 따라 알고리즘의 성공 여부가 달라진다.

폴라드 p-1 소인수분해법과 비교

폴라드 p-1 소인수분해법에서는 페르마의 소정리와 모듈러산술에서의 거듭제곱을 이용하여 소인수를 찾는다. 소인수를 발견할 조건은 $p-1\mid E$이다. 한편 본 문서에서 소개한 방법은 $p-\delta \mid E$의 성립 여부이다. 이때 $\delta =\left({\frac {D}{p}}\right)$는 ±1이므로, 결국에는 $p\pm 1\mid E$를 목표로 찾아다니는 셈이 된다.

어떤 소인수 $p$에 대해 $p\pm 1$을 소인수분해할 때, 더 자잘한 소수의 거듭제곱들로 쪼개지는 쪽이 더 다루기 쉽다. 이를테면 $p=1009$일 때, $p-1=2^{4}\cdot 3^{2}\cdot 7,p+1=2\cdot 5\cdot 101$이다. 전자는 가장 큰 덩어리가 2의 4제곱, 즉 16이고, 후자는 101이 가장 크다. 이 말은 즉 $E=\operatorname {lcm} (2,3,\cdots B)$를 셈할 때 $p\pm 1\mid E$가 성립하기 위한 최소 $B$는 $p-1$의 경우 16, $p+1$의 경우 101이다. 만약 $B=20$으로 둔다면 $p-1$은 알고리즘이 성공하지만 $p+1$은 성공하지 못한다.

그런데 사실 $p-1$을 다루기 쉬운 소인수는 폴라드 p-1 소인수분해법을 쓰는 것이 빠르다. 앞서 알고리즘을 소개할 때 $(V_{n},V_{n+1})$의 다음 항인 $(V_{2n},V_{2n+1}){\text{ or }}(V_{2n+1},V_{2n+2})$를 셈할 때에는 두 개 항을 계산해야 한다. 하지만 폴라드의 방법은 밑이 고정된 거듭제곱, 즉 $a^{E}-1\mod N$을 셈하는 것이기에, $a^{n}$ 다음 항인 $a^{2n}{\text{ or }}a^{2n+1}$을 계산하려면 그 값을 제곱하고 필요시 원래 밑을 곱해주면 된다. 즉 계산할 변수가 하나이기에, 같은 $B,E$라도 윌리엄스의 방법보다 연산량이 절반 가량 적다.

더구나 폴라드의 방법에서는 $p\mid N,p-1\mid E$이면 무조건 $a^{E}\equiv 1{\pmod {N}}$을 만족하지만, 이쪽은 $p-1\mid E$이더라도 절반의 확률로 초깃값 $P$에 대해 $\delta =-1$이면 $V_{p+1}\equiv 2{\pmod {N}}$이 되어서 알고리즘은 수포로 돌아간다.

따라서 윌리엄스의 방법은 보통 폴라드의 방법에서 찾기 매우 어려운 경우, 즉 $p+1\mid E$인 상황에 주로 관심을 두고 있으며, 이것이 윌리엄스 p+1 소인수분해법이라 불리는 이유이다.

초기 조건을 설정할 때 유의사항

초깃값은 반드시 3 이상으로 잡는다. $P=2$이면 뤼카 수열은 $V_{n}(2,1):2,2,2,\cdots$와 같이 모든 항이 2가 되며, $P=1$이면 $V_{n}(1,1):2,1,-1,-2,-1,1,\cdots$과 같이 주기가 6인 수열이 된다. 이렇게 되면 $p,q\mid N$인 서로 다른 두 소인수에 대해 $p\mid V_{E}-2,q\nmid V_{E}-2$ 혹은 반대 조건을 이끌어낼 수가 없다.

특정 소인수 $p$의 입장에서 자기와 바로 이웃한 수인 $p\pm 1$이 $E$의 타겟이다. 앞서 언급한 소인수인 4079의 경우, $p-1$이 타겟이면 $E\geq 2039$일 때 $p-1\mid E$를 만족하지만 $p+1$이 타겟이면 $E\geq 17$일 때 $p+1\mid E$가 된다. 둘 중 $E$의 하한선이 낮은 쪽이 소인수를 잡아내기 쉬운 값이다. 그렇기에 윌리엄스의 방법으로 소인수를 찾을 때에는 $E$가 $p\pm 1$양쪽에 접근할 수 있도록 설계해야 한다.

폴라드 p-1 소인수분해법에서는 $E$의 타겟이 $a$에 관계 없이 $p-1$로 일정하기에, 이 방법으로 찾아내지 못한 소인수들에 대해서는 $p+1$이 타겟이 되도록 $P,D=P^{2}-4$를 정해야 한다. 즉 $\delta (D,p)=\left({\frac {D}{p}}\right)=-1$을 목표로 한다.

가령 $P=3$을 가정했다면 $D=5$이고, $p\equiv \pm 2{\pmod {5}}\Leftrightarrow \delta (5,p)=-1$이면 $p+1$이 타겟이 된다. 하지만 $p\equiv \pm 2{\pmod {5}}\Leftrightarrow \delta (5,p)=1$이면 타겟은 $p-1$이므로, 이걸로는 $p+1$에 접근하지 못한다.

이번에는 $(P,D)=(4,12)$를 넣고 다시 시도한다. 이 경우 $\delta (12,p)=\delta (3,p)$의 부호에 따라 $p+1$ 접근 여부가 달라진다. $p\equiv \pm 5{\pmod {12}}\Leftrightarrow \delta (3,p)=-1$이면 이 단계에서 $p+1$에 접근 가능하지만, 그렇지 않으면 초깃값을 또 바꿔야 한다.

$(P,D)=(7,45)$이면 $(P,D)=(3,5)$일 때와 알고리즘 중복으로 '의미 없는 시행'이 된다. 모든 홀수 소수에 대해 $\delta (45,p)=\delta (5,p)$이기 때문이다. 또, $(P,D)=(3,5),(4,12)$를 시도했다면 이 단계에서 $p+1$에 접근하지 못한 소인수들은 $\delta (3,p)=\delta (5,p)=1$인 그룹이다. 그러면 자동으로 $\delta (15,p)=\delta (60,p)=1$이 성립하므로 $(P,D)=(8,60)$ 역시 시도할 필요가 없다.

중요한 것은 $P,D$의 값을 달리할 때 $\delta (D,p)$가 이전 시행들과 독립된 식이 되도록 맞추는 것이다.

한계점

실제로는 $p\pm 1$두 값 모두 위 방법으로 잡아내지 못하는 소수가 많이 존재하기에, 이 경우 알고리즘이 성공하기 매우 어렵다.

가령 $N=pq=3391934713,p=50207,q=67559$의 경우 $p-1=2\cdot 13\cdot 1931,p+1=2^{5}\cdot 3\cdot 523$인데 양쪽 모두 큰 소인수를 포함하고 있다. 다른 소인수도 마찬가지: $q-1=2\cdot 17\cdot 1987,q+1=2^{3}\cdot 3\cdot 5\cdot 563$ 이렇게 되면 그나마 최대 소인수가 가장 작은 $p+1$을 공략하더라도 $B\geq 523$으로 잡아야 소인수를 잡아낼 수 있다.

특수한 경우가 아닌 이상 보통은 활용도가 높은 렌스트라 타원곡선 소인수분해법이나 이차 체를 많이 이용한다. 전자의 경우 특정 소인수를 잡기 위한 타겟을 $p\pm 1$ 말고도 여러 값으로 바꾸어갈 수 있다.

변칙 알고리즘

최적화 방법에 따라 알고리즘 단계나 계산 방식을 적절히 변형할 수 있다.

항 연산 분리

$E$의 값은 기본적으로 최소공배수 연산으로 고르지만, 여기에 2, 3, 5의 거듭제곱을 따로 분리해서 연산 방식을 달리할 수 있다.

이를테면 $B=20,E=2^{4}\cdot 3^{2}\cdot 5\cdot E',E'=323323$이라 할 때, $E'$은 7 이상의 소인수들의 곱으로만 이루어져 있다. 이때 $V_{E'}\mod N$을 먼저 셈한 다음 $V_{E}$를 이끌어낸다면 연산량을 단축할 수 있다.

그 이유는 위의 "수열의 특정 항을 셈하는 방법"의 알고리즘에 있다. 일반적으로 $V_{n}$으로부터 $V_{2n}{\text{ or }}V_{2n+1}$을 이끌어내고자 한다면 순서쌍 $(V_{n},V_{n+1})$을 이용해 두 항을 같이 계산해야 한다. (이때 곱셈 2회를 시행한다) 하지만 2, 3, 5만을 소인수로 가지는 $A$에 대해 $V_{n}\to V_{An}$을 이끌어내려고 한다면, 항 하나로만 연산을 셈하면 된다.

• ⓐ $V_{2n}=V_{n}^{2}-2$: 곱셈 1회 시행
• ⓑ $V_{3n}=(V_{n}^{2}-3)V_{n}$: 곱셈 2회 시행
• ⓒ $V_{5n}=[(V_{n}^{2}-5)V_{n}^{2}+5]V_{n}$: 곱셈 3회 시행
  • $v=V_{n}^{2}$을 먼저 셈하고 $V_{5n}=[(v-5)v+5]V_{n}$을 계산하면 곱셈 횟수는 1+2회이다.

일반적으로 다음 항 계산을 시행한다는 것은 $E$의 비트를 하나 읽는 것과 등가이다. 앞서 든 예시를 들자면 $E=1101111000000010000111110000_{(2)}$은 28비트이므로 원래 알고리즘을 따르면 $V_{E}$에 도달하기까지 곱셈을 총 56회 시행한다. 반면 $E'=1001110111011111011_{(2)}$은 19비트이고 $V_{E'}$에 이르기까지 곱셈 횟수는 38회이다. 또, $V_{E'}\to V_{5E'}$ 단계는 위 ⓒ 방법으로 곱셈 3회, $V_{5E'}\to V_{45E'}$ 단계는 ⓑ 방법×2로 곱셈 4회, 마지막으로 $V_{45E'}\to V_{E}$ 단계는 ⓐ 방법×4로 곱셈 4회를 시행하므로, 모두 합하면 49회이다.

$E$ 내에 포함된 작은 소인수들이 많이 들어갈수록 곱셈 횟수를 많이 단축할 수 있다. 같은 방법으로 $V_{7n}$을 단항 계산으로 전환하면 연산량은 더 단축되지만 소수 배율이 더 커지면 단축 효과는 떨어진다.

계산 방식 바꾸기

앞서 소개한 방법은 제2종 뤼카 수열을 이용했지만, 사실 이는 무리수의 거듭제곱 표현으로 바꿔 쓸 수 있다. $V_{1}$이 짝수인 경우,

$V_{n}(2P',1)=\alpha ^{n}+\alpha ^{-n},\alpha =P'+{\sqrt {D}},D=P'^{2}-1$

식에서 기본 알고리즘에서는 $V_{n}$을 셈하는 것이었지만 여기서는 $\alpha ^{n}$을 직접 셈한다. 물론 $\alpha \in \mathbb {Q} ({\sqrt {D}})$이면 $\alpha ^{n}\in \mathbb {Q} ({\sqrt {D}})$이므로, 실제로는 $\alpha ^{n}=H_{n}+I_{n}{\sqrt {D}}$에서 $(H_{n},I_{n})$을 계산 및 기록한다.

이때 역수는 $\alpha ^{-n}=H_{n}-I_{n}{\sqrt {D}}$이므로 $2H_{n}=V_{n}$이며, 나아가 $p$가 소수이면 $H_{p-\delta }\equiv 1{\pmod {p}}$도 성립한다.

아울러 $\alpha ^{m+n}=\alpha ^{m}\alpha ^{n}$을 $H_{n},I_{n}$에 관한 식으로 바꾸면 $(H_{m+n},I_{m+n})=(H_{m},I_{m})\cdot (H_{n},I_{n})=(H_{m}H_{n}+DI_{m}I_{n},H_{m}I_{n}+I_{m}H_{n})$이다. 또, 초깃값은 $H_{1}=P',I_{n}=1$이다.

• 항 번호를 두 배로 뛰기: $(H_{2n},I_{2n})=(H_{n},I_{n})^{2}=(H_{n}^{2}+DI_{n}^{2},2H_{n}I_{n})=(2H_{n}^{2}-1,2H_{n}I_{n})$
• 다음 항 셈하기: $(H_{n+1},I_{n+1})=(H_{n},I_{n})\cdot (P',1)=(P'H_{n}+DI_{n},P'I_{n}+H_{n})$

이렇게 해서 $H_{E}-1\mod N$을 구하고 $\gcd(H_{E}-1,N)$으로부터 비자명한 약수를 찾아내면, 알고리즘은 성공한다. 마찬가지로 모든 곱셈 및 덧셈은 $\mathbb {Z} /N\mathbb {Z}$상에서 이루어진다.

두 단계 분할

폴라드 p-1 소인수분해법과 마찬가지로 알고리즘을 두 단계로 나눌 수 있다. $p-\delta =r_{1}r_{2}\cdots r_{k},r_{1}<r_{2}<\cdots <r_{k}$가 소수 또는 소수의 거듭제곱들의 곱일 때, $B_{1}\geq r_{k-1},B_{2}\geq r_{k}$이 되도록 기준치를 설정하고 아래 방법을 따라가면 원하는 약수를 찾을 수 있다.

두 단계 알고리즘에는 여러 방식이 있지만 여기서는 바로 위 문단의 것을 기준으로 서술한다. 1단계까지는 $H_{E}\mod N$을 셈하고, 2단계에서는 $B_{1}<s_{j}\leq B_{2}$인 모든 소수 $s_{j}$에 대해 $\prod _{s_{j}}(H_{Es_{j}}-1)\mod N$을 계산한다.

• 기본 알고리즘과 같이 첫째 목표치 $B_{1}$을 지정한다.
• 이 기준치에 대응하는 항 번호인 $E=\prod _{{\text{primes }}q\leq B_{1}}q^{\lfloor \log _{q}B_{1}\rfloor }$를 셈한다.
• 초깃값 $H_{1}=P'$을 지정하고 위 기본 알고리즘으로 $H_{E}-1,I_{E}\mod N$을 셈한다.
• 여기까지가 1단계이다. 만약 $\gcd(H_{E}-1,N)$으로부터 소인수를 찾으면, 여기서 알고리즘을 종료할 수 있다. 약수를 찾지 못했다면 아래 2단계로 이어진다.
• $(H_{E},I_{E})^{s}=(H_{sE},I_{sE})$ 식을 이용하여 $(H_{2E},I_{2E}),(H_{4E},I_{4E}),(H_{6E},I_{6E}),\cdots \mod N$의 값을 메모리에 가급적 많이 적어둔다.
• $B_{1}<s_{j}\leq B_{2}$내의 소수 또는 홀수 소수의 거듭제곱 목록을 작성하고 이를 오름차순으로 정렬한다.
• $(H_{s_{1}E},I_{s_{1}E})=(H_{E},I_{E})^{s_{1}}$을 셈하고 $T=H_{s_{1}E}-1$을 저장한다.
• $d_{j}=s_{j+1}-s_{j}\ (j\geq 1)$이라 할 때, 메모리에 적어둔 $(H_{d_{j}E},I_{d_{j}E})$를 불러와서 $(H_{s_{j+1}E},I_{s_{j+1}E})=(H_{s_{j}E},I_{s_{j}E})\cdot (H_{d_{j}E},I_{d_{j}E})$를 셈한 후 $T\leftarrow T(H_{s_{j+1}E}-1)$와 같이 값을 갱신한다.
• 이렇게 모든 $s_{j}$에 대해 계산을 반복하고 나면 $T$가 바로 2단계의 목표이다. $\gcd(T,N)$으로부터 비자명한 약수를 얻어내면 알고리즘은 성공한다.

같이 보기

• 폴라드 p-1 소인수분해법
• 렌스트라 타원곡선 소인수분해법