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

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 알고리즘
3. 원리
- 3.1. 근사분수
- 3.2. 관계식
4. 확장
5. 예시
6. 활용
참조

1. 개요

연분수 소인수분해 알고리즘은 주어진 합성수를 소인수분해하는 알고리즘으로, 합성수 n의 제곱근을 연분수로 전개하여 계산한다. 이 알고리즘은 점화식을 반복적으로 계산하며, k가 짝수이고 t_k가 완전제곱수가 될 때, $p_{k-1}^2$ 과 $y^2$ 의 합동 관계를 이용하여 n의 비자명한 약수를 찾는다. 만약 약수를 찾을 수 없으면, 다른 소인수분해 알고리즘을 사용한다. 연분수 소인수분해 알고리즘은 이차 체와 같이 t_k들을 소인수분해하여 완전제곱수를 찾는 방식으로 확장될 수 있으며, n 대신 m*n의 연분수 전개를 사용할 수도 있다.

더 읽어볼만한 페이지

소인수 분해 알고리즘 - 쇼어 알고리즘
쇼어 알고리즘은 소인수분해 및 이산 로그 문제를 해결하는 양자 알고리즘으로, 양자 위상 추정 알고리즘과 연분수 알고리즘을 활용하며, 공개 키 암호화 방식을 깨뜨릴 수 있다.
소인수 분해 알고리즘 - 특수 수체 체
특수 수체 체는 작은 계수 다항식으로 표현되는 특정 형태의 큰 정수를 효율적으로 소인수분해하는 알고리즘으로, 정수 계수 기약 다항식과 특정 정수를 선택하여 대수적 수체의 인수 기저를 활용하는 체질 과정을 거친다.

연분수 소인수분해 알고리즘
개요
클래스 그룹 기반 방법
알고리즘 종류	딕슨 알고리즘 연분수 소인수분해 알고리즘 이차 체 클래스 그룹 소인수 분해
역사
개발자	모리스 크라이칙
발표 년도	1926년
기타 정보
후계 알고리즘	이차 체

2. 알고리즘

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

소인수분해할 합성수 n에 대하여 연분수 전개를 계산하고, 점화식을 이용하여 소인수를 판별한다. 자세한 단계는 하위 섹션에서 설명한다.

2. 1. 기본 단계

1. 소인수분해할 합성수 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\geq0)

:

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

:

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

:단, 모든 계산은 n으로 나눈 나머지만 고려한다. (mod n)

4. 3번 과정은 k가 짝수이면서

t_k

가 완전제곱수가 될 때까지 반복한다.

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를 찾거나, 타원곡선 알고리즘, 폴라드 로 알고리즘, 이차 체 등 다른 소인수분해 알고리즘을 실행한다.

2. 2. 점화식

점화식의 초깃값은 다음과 같이 주어진다.

:

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

다음으로, 점화식을 다음과 같이 계산한다.

:

a_{k+1}=\lfloor x_{k+1} \rfloor ,

x_{k+1}=\frac {1}{x_k-a_k} \ \ \ (k\geq0)

:

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

:

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

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

2. 3. 소인수 판별

3번 과정에서 k가 짝수이면서 t_k^영어가 완전제곱수가 될 때까지 3번 과정을 반복한다. 이때, t_k^영어 = y²이라 하면 p_k-1²^영어 ≡ y²^영어 (mod 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를 찾아서 계산하거나, 타원곡선 알고리즘, 폴라드 로 알고리즘, 이차 체 등의 다른 소인수분해 알고리즘을 실행해도 된다.

3. 원리

Square root of|√^영어''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+...}}}$ 으로 표현될 수 있을 때, 연분수의 k번째 근사분수 C_k는 특정한 관계식을 만족하며, 이 관계식을 이용하여 n을 소인수분해할 수 있다.

3. 1. 근사분수

연분수의 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)^kt_k \ \ \ (k\geq1)

,

p_{k-1}^2\equiv(-1)^kt_k \pmod{n}

여기서 k>0이면서 k가 짝수이고 t_k가 제곱수이면,

p_{k-1}^2\equiv y^2 \pmod{n}

의 형태가 되어 n을 소인수분해할 수 있게 된다.

3. 2. 관계식

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

\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}

이때, 다음의 관계식이 성립한다.^[1]

:

p_{k-1}^2-nq_{k-1}^2=(-1)^kt_k \ \ \ (k\geq1)

,

p_{k-1}^2\equiv(-1)^kt_k \pmod{n}

여기서 k>0이면서 k가 짝수이고 t_k가 제곱수이면,

p_{k-1}^2\equiv y^2 \pmod{n}

의 형태가 되어 n을 소인수분해할 수 있게 된다.^[1]

4. 확장

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

5. 예시

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

연분수 소인수분해 알고리즘
k^영어	0	1	2	3	4	5	6	7	8
a_k^영어	58	1	1	5	1	1	1	16	12
s_k^영어	0	58	5	49	46	23	19	54	58
t_k^영어	1	63	54	19	69	42	73	7	9
p_k^영어	58	59	117	644	761	1405	2166	3582	44154

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

p₇²^영어 ≡ t₈^영어 (mod n^영어), 즉 1791² ≡ 3² (mod 3427)

1791² ≡ 3² (mod 3427)이 성립하므로 1791² - 3² ≡ 0 (mod 3427), (1791 + 3) ⋅ (1791 - 3) ≡ 0 (mod 3427)이 된다. 최대공약수(1791 + 3, 3427) = 23, gcd(1791 - 3, 3427) = 149이므로 23과 149가 n^영어 = 3427의 약수가 되며, 23과 149는 둘 다 소수이므로 n^영어 = 3427 = 23 ⋅ 149가 된다.

6. 활용

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

참조

_[1] 논문 On Factoring Large Numbers
_[2] 논문 A Method of Factoring and the Factorization of ''F''₇ https://www.ams.org/[...] American Mathematical Society 1975-01
_[3] 뉴스 A Tale of Two Sieves https://www.ams.org/[...] 1996-12

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com