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

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

아이디어

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

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

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

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

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

알고리즘

소인수분해를 하려는 합성수 [math]\displaystyle{ N }[/math]을 입력 받고 아래 과정을 시행한다.

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

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

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

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

[math]\displaystyle{ V_{2n}=V_n^2-2, V_{2n+1}=V_nV_{n+1}-P }[/math]

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

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

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

이렇게 계산과 변수 갱신을 반복하면 [math]\displaystyle{ x=V_E \mod N }[/math]에 도달한다.

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

• [math]\displaystyle{ (x, y)=(V_0, V_1) }[/math]
• 비트 1: ⓑ→ [math]\displaystyle{ (x, y)=(V_1, V_2) }[/math]
• 비트 1: ⓑ→ [math]\displaystyle{ (x, y)=(V_3, V_4) }[/math]
• 비트 0: ⓐ→ [math]\displaystyle{ (x, y)=(V_6, V_7) }[/math]
• 비트 1: ⓑ→ [math]\displaystyle{ (x, y)=(V_{13}, V_{14}) }[/math]
• 비트 0: ⓐ→ [math]\displaystyle{ (x, y)=(V_{26}, V_{27}) }[/math]
• 이렇게 비트를 계속 추적해 나가면 마지막에는 [math]\displaystyle{ (x, y)=(V_{420}, V_{421}) }[/math]을 얻고, 이때 [math]\displaystyle{ x }[/math]의 값이 계산 목표이다.

적용 예

[math]\displaystyle{ N=31910017 }[/math]을 소인수분해하려고 한다.

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

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

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

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

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

초기 조건이 다르다면

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

한계점

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

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

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

변칙 알고리즘

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

항 연산 분리

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

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

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

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

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

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

계산 방식 바꾸기

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

[math]\displaystyle{ V_n(2P', 1)=\alpha^n+\alpha^{-n}, \alpha=P'+\sqrt{D}, D=P'^2-1 }[/math]

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

이때 역수는 [math]\displaystyle{ \alpha^{-n}=H_n-I_n\sqrt{D} }[/math]이므로 [math]\displaystyle{ 2H_n=V_n }[/math]이며, 나아가 [math]\displaystyle{ p }[/math]가 소수이면 [math]\displaystyle{ H_{p-\delta} \equiv 1 \pmod p }[/math]도 성립한다.

아울러 [math]\displaystyle{ \alpha^{m+n}=\alpha^m\alpha^n }[/math]을 [math]\displaystyle{ H_n, I_n }[/math]에 관한 식으로 바꾸면 [math]\displaystyle{ (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]\displaystyle{ H_1=P', I_n=1 }[/math]이다.

• 항 번호를 두 배로 뛰기: [math]\displaystyle{ (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]\displaystyle{ (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]\displaystyle{ H_E-1 \mod N }[/math]을 구하고 [math]\displaystyle{ \gcd(H_E-1, N) }[/math]으로부터 비자명한 약수를 찾아내면, 알고리즘은 성공한다. 마찬가지로 모든 곱셈 및 덧셈은 [math]\displaystyle{ \mathbb{Z}/N\mathbb{Z} }[/math]상에서 이루어진다.

두 단계 분할

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

두 단계 알고리즘에는 여러 방식이 있지만 여기서는 바로 위 문단의 것을 기준으로 서술한다. 1단계까지는 [math]\displaystyle{ H_E \mod N }[/math]을 셈하고, 2단계에서는 [math]\displaystyle{ B_1 \lt s_j \leq B_2 }[/math]인 모든 소수 [math]\displaystyle{ s_j }[/math]에 대해 [math]\displaystyle{ \prod_{s_j} (H_{Es_j}-1) \mod N }[/math]을 계산한다.

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

같이 보기

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