연분수 소인수분해 알고리즘 문서 원본 보기

{{위키데이터 속성 추적}}
'''연분수 소인수분해 알고리즘'''은 어떤 [[자연수]]의 [[제곱근]]의 [[연분수]] 전개를 이용하여 자연수를 [[소인수분해]]하는 [[알고리즘]]이다.

== 알고리즘 ==
연분수 소인수분해 알고리즘은 다음과 같다.

1. 소인수분해하고 싶은 합성수를 n이라고 하자. 이때, 이 n에 대하여 <math>\sqrt{n}=[a_0; a_1, a_2, a_3, ...]=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+...}}}</math>이라고 표현될 수 있다.


2. [[점화식]]들의 초깃값을 다음과 같이 준다.

<math>x_0 = \sqrt{n}, a_0 = \lfloor x_0 \rfloor, p_{-2}=0, p_{-1}=1, s_0=0, t_0=1</math>


3. 다음으로, 다음과 같이 점화식을 계산해 나간다.

<math>a_{k+1}=\lfloor x_{k+1} \rfloor ,</math> <math>x_{k+1}=\frac {1}{x_k-a_k} \ \ \ (k\geq0)</math>

<math>p_{k+1}=a_{k+1}p_k+p_{k-1},</math>

<math>s_{k+1}=a_kt_k-s_k, t_{k+1}=(n-s_{k+1}^2)/t_k \ \ \ (k\geq0)</math> 

단, 여기서 모든 계산은 n으로 나눈 나머지만을 생각한다는 것에 주의한다. 즉, 모든 계산에는 (mod n)이 들어간다는 것에 주의한다. 


4. 3번 과정에서 k가 짝수이면서 t<sub>k</sub>가 완전제곱수가 될 때까지 3번 과정을 반복한다. 이때, <math>t_k=y^2</math>라 하면 <math>p_{k-1}^2\equiv y^2 \pmod{n}</math>가 되므로 1 < gcd(p<sub>k-1</sub>-y, n) < n이면 gcd(p<sub>k-1</sub>-y, n)가 n의 비자명한 약수가 되고, 1 < gcd(p<sub>k-1</sub>+y, n) < n이라면 gcd(p<sub>k-1</sub>+y, n)가 n의 비자명한 약수가 된다 (둘 다 비자명한 약수가 될 수도 있지만 이런 경우 두 수가 같은 경우도 있을 수 있다). 만약 두 개의 값 모두 1이거나 n이라면 t<sub>k</sub>가 제곱수가 되는 다른 k를 찾아서 계산하거나, [[렌스트라의 타원곡선 알고리즘|타원곡선 알고리즘]]이나 [[폴라드 로 알고리즘]], [[이차 체]] 등의 다른 소인수분해 알고리즘을 실행해도 된다.

== 원리 ==
<math>\sqrt{n}=[a_0; a_1, a_2, a_3, ...]=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+...}}}</math>으로 표현될 수 있을 때, <math>\sqrt{n}</math>의 ''k번째 근사분수 C<sub>k</sub>''는 다음과 같이 정의된다. 

<math>C_k=[a_0;a_1, a_2,...,a_k]=\frac{p_k}{q_k}</math>

여기서 q<sub>k</sub>는 다음과 같이 점화식의 형태로 정의되는 양이다.

<math>q_{-2}=1, q_{-1}=0, q_{k+1}=a_{k+1}q_k+q_{k-1}</math>

이때, 다음의 관계식이 성립한다.

<math>p_{k-1}^2-nq_{k-1}^2=(-1)^kt_k \ \ \ (k\geq1)</math>, <math>p_{k-1}^2\equiv(-1)^kt_k \pmod{n}</math>

여기서 k>0이면서 k가 짝수이고 t<sub>k</sub>가 제곱수이면, <math>p_{k-1}^2\equiv y^2 \pmod{n}</math>의 형태가 되어 n을 소인수분해할 수 있게 된다. 

== 확장 ==
연분수 소인수분해 알고리즘에서 t<sub>k</sub>가 완전제곱수로 딱 떨어지지 않는 경우가 계속 나올 수도 있는데, 그런 경우 [[이차 체]]처럼 t<sub>k</sub>들을 소인수분해해 보아 곱했을 때 완전제곱수가 되는 t<sub>k</sub>들을 찾은 뒤 관계식을 곱하여 소인수분해하는 방식으로 적용해도 된다. 또한 n의 제곱근의 연분수 전개를 구하지 않고 n에다가 소수 또는 작은 여러 개의 소수들의 곱인 m을 곱한 수의 연분수 전개를 이용하여 알고리즘을 적용할 수도 있다.

== 예시 ==
n = 3427이라 하고, 점화식의 각 항들을 토대로 표로 정리하면 다음과 같다.
{| class="wikitable"
|+연분수 소인수분해 알고리즘
!k
!0
!1
!2
!3
!4
!5
!6
!7
!8
|-
|a<sub>k</sub>
|58
|1
|1
|5
|1
|1
|1
|16
|12
|-
|s<sub>k</sub>
|0
|58
|5
|49
|46
|23
|19
|54
|58
|-
|t<sub>k</sub>
|1
|63
|54
|19
|69
|42
|73
|7
|9
|-
|p<sub>k</sub>
|58
|59
|117
|644
|761
|1405
|2166
|1791
|3096
|}
여기서 k가 짝수이면서 t<sub>k</sub>가 완전제곱수가 되는 첫 번째 k는 8이다. 즉, 다음의 관계식이 성립한다.

<math>p_7^2 \equiv t_8 \pmod{n},\ \ \ 1791^2 \equiv 3^2 \pmod{3427} </math>

1791<sup>2</sup> ≡ 3<sup>2</sup> (mod 3427)이 성립하므로 1791<sup>2</sup> - 3<sup>2</sup> ≡ 0 (mod 3427), (1791 + 3) ⋅ (1791 - 3) ≡ 0 (mod 3427)이 된다. gcd(1791 + 3, 3427) = 23, gcd(1791 - 3, 3427) = 149이므로 23과 149가 n = 3427의 약수가 되며, 23과 149는 둘 다 소수이므로 n = 3427 = 23 ⋅ 149가 된다.

== 활용 ==
마이클 모리슨 (Michael Morrison)과 존 브릴하트 (John Brillhart)는 [[페르마 수]] F<sub>7</sub> = 340282366920938463463374607431768211457을 소인수분해할 때 257 ⋅ F<sub>7</sub>의 연분수 전개와 그 과정에서 나오는 1,300,000개 가량의 t<sub>k</sub>를 이용하여 제곱수가 되는 곱을 구하고 이 수를 소인수분해하였다.

== 같이 보기 ==
* [[연분수]]
* [[소인수분해]]
* [[렌스트라의 타원곡선 알고리즘|타원곡선 소인수분해 알고리즘]]
* [[이차 체]]
* [[수체 체]]
* [[소수 (수론)|소수]]와 [[합성수]]
{{수론 알고리즘}}

[[분류:소인수 분해 알고리즘]]