연분수 소인수분해 알고리즘

연분수 소인수분해 알고리즘은 어떤 자연수의 제곱근의 연분수 전개를 이용하여 자연수를 소인수분해하는 알고리즘이다.

알고리즘

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

1. 소인수분해하고 싶은 합성수를 n이라고 하자. 이때, 이 n에 대하여 ${\sqrt {n}}=[a_{0};a_{1},a_{2},a_{3},...]=a_{0}+{\frac {1}{a_{1}+{\frac {1}{a_{2}+{\frac {1}{a_{3}+...}}}}}}$이라고 표현될 수 있다.

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

$x_{0}={\sqrt {n}},a_{0}=\lfloor x_{0}\rfloor ,p_{-2}=0,p_{-1}=1,s_{0}=0,t_{0}=1$

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

$a_{k+1}=\lfloor x_{k+1}\rfloor ,$ $x_{k+1}={\frac {1}{x_{k}-a_{k}}}\ \ \ (k\geq 0)$

$p_{k+1}=a_{k+1}p_{k}+p_{k-1},$

$s_{k+1}=a_{k}t_{k}-s_{k},t_{k+1}=(n-s_{k+1}^{2})/t_{k}\ \ \ (k\geq 0)$

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

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

원리

${\sqrt {n}}=[a_{0};a_{1},a_{2},a_{3},...]=a_{0}+{\frac {1}{a_{1}+{\frac {1}{a_{2}+{\frac {1}{a_{3}+...}}}}}}$으로 표현될 수 있을 때, ${\sqrt {n}}$의 k번째 근사분수 C_k는 다음과 같이 정의된다.

$C_{k}=[a_{0};a_{1},a_{2},...,a_{k}]={\frac {p_{k}}{q_{k}}}$

여기서 q_k는 다음과 같이 점화식의 형태로 정의되는 양이다.

$q_{-2}=1,q_{-1}=0,q_{k+1}=a_{k+1}q_{k}+q_{k-1}$

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

$p_{k-1}^{2}-nq_{k-1}^{2}=(-1)^{k}t_{k}\ \ \ (k\geq 1)$, $p_{k-1}^{2}\equiv (-1)^{k}t_{k}{\pmod {n}}$

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

확장

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

예시

n = 3427이라 하고, 점화식의 각 항들을 토대로 표로 정리하면 다음과 같다.

연분수 소인수분해 알고리즘

k	0	1	2	3	4	5	6	7	8
ak	58	1	1	5	1	1	1	16	12
sk	0	58	5	49	46	23	19	54	58
tk	1	63	54	19	69	42	73	7	9
pk	58	59	117	644	761	1405	2166	1791	3096

여기서 k가 짝수이면서 t_k가 완전제곱수가 되는 첫 번째 k는 8이다. 즉, 다음의 관계식이 성립한다.

$p_{7}^{2}\equiv t_{8}{\pmod {n}},\ \ \ 1791^{2}\equiv 3^{2}{\pmod {3427}}$

1791² ≡ 3² (mod 3427)이 성립하므로 1791² - 3² ≡ 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₇ = 340282366920938463463374607431768211457을 소인수분해할 때 257 ⋅ F₇의 연분수 전개와 그 과정에서 나오는 1,300,000개 가량의 t_k를 이용하여 제곱수가 되는 곱을 구하고 이 수를 소인수분해하였다.

같이 보기

• 연분수
• 소인수분해
• 타원곡선 소인수분해 알고리즘
• 이차 체
• 수체 체
• 소수와 합성수