수체 체

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

1. 개요
2. 역사
3. 작동 원리
4. 구현
- 4.1. 주요 구현체
- 4.2. 분산 컴퓨팅
참조

1. 개요

수체 체(Number field sieve, NFS)는 정수를 소인수분해하는 데 사용되는 가장 빠른 알고리즘 중 하나이다. 이 알고리즘은 대수적 수체와 체질(sieve) 기술을 활용하며, 특히 큰 수의 소인수분해에 효과적이다. NFS는 특수 수체 체(SNFS)와 일반 수체 체(GNFS)의 두 가지 주요 변형이 있다. GNFS는 다항식 선택, 체질, 선형 대수, 제곱근 계산 등의 단계를 거쳐 소인수를 찾는다. 다항식 선택은 알고리즘 성능에 중요한 영향을 미치며, 머피와 브렌트, 클라인중 등의 방법이 사용된다. NFS는 분산 컴퓨팅 환경에서 구현되며, msieve, GGNFS 등의 구현체가 존재한다.

더 읽어볼만한 페이지

소인수 분해 알고리즘 - 쇼어 알고리즘
쇼어 알고리즘은 소인수분해 및 이산 로그 문제를 해결하는 양자 알고리즘으로, 양자 위상 추정 알고리즘과 연분수 알고리즘을 활용하며, 공개 키 암호화 방식을 깨뜨릴 수 있다.
소인수 분해 알고리즘 - 연분수 소인수분해 알고리즘
연분수 소인수분해 알고리즘은 합성수 $n$ 의 제곱근을 연분수로 전개하여 얻은 값으로 $x^2 \equiv y^2 \pmod n$ 를 만족하는 $x$ 와 $y$ 를 찾아 $n$ 의 약수를 구하는 알고리즘이다.

수체 체
개요
유형	소인수 분해 알고리즘
클래스	수론적 알고리즘
고안자	존 폴라드
발간일	1988년
효율성
시간 복잡도	+o(1)\right)(\log n)^{\frac {1}{3}}(\log \log n)^{\frac {2}{3}}\right)\right)}}
적용 대상	10진수 100자리 이상의 정수
세부 정보
전제 조건	큰 정수의 인수 분해 문제
후속 알고리즘	이산 로그 문제 해결에 응용 가능
기타
관련 알고리즘	이차 체 다항식 체 특수 수체 체 쇼어 알고리즘

2. 역사

주어진 원본 소스(source)에 내용이 없으므로, 섹션 내용을 작성할 수 없습니다. (이전 응답과 동일)

3. 작동 원리

일반 숫자체 체(GNFS) 알고리즘은 큰 정수를 소인수분해하는 데 사용되는 가장 효율적인 알고리즘 중 하나이다. GNFS의 작동 원리는 다음과 같다.

1. 다항식 선택: 작은 차수 ''d''와 ''e''를 갖는 두 개의 다항식 ''f''(''x'')와 ''g''(''x'')를 선택한다. 이 다항식들은 정수 계수를 가지며, 유리수 상에서 기약 다항식이어야 하고, ''n''을 법으로 할 때 공통 정수 근 ''m''을 가져야 한다. 이러한 다항식을 선택하는 최적의 방법은 알려져 있지 않지만, 머피와 브렌트의 방법 또는 클라인융의 방법과 같이 효율적인 방법들이 사용된다.

2. 체질: 수체 링 '''Z'''[''r''₁]와 '''Z'''[''r''₂]를 고려한다. 여기서 ''r''₁과 ''r''₂는 각각 다항식 ''f''와 ''g''의 근이다. 목표는 ''r'' = ''b''^''d''·''f''(''a''/''b'')와 ''s'' = ''b''^''e''·''g''(''a''/''b'')가 선택된 소수 기반에 대해 동시에 smooth number가 되게 하는 정수 ''a''와 ''b'' 값을 찾는 것이다. 이 과정은 lattice sieving과 같은 방법을 사용하여 수행된다.

3. 선형 대수: 체질 단계에서 충분한 수의 (a, b) 쌍을 찾은 후, 가우스 소거법 또는 블록 란초스 알고리즘, 블록 비데만 알고리즘과 같은 희소 행렬 해결 알고리즘을 사용하여 특정 ''r''과 해당 ''s''의 곱이 동시에 제곱수가 되도록 하는 선형 결합을 찾는다. 이 때, 각 곱은 수체에서의 제곱수의 노름이라는 조건이 추가로 필요하다.

4. 제곱근 계산: 앞선 단계에서 찾은 선형 결합을 바탕으로, ''a'' − ''r''₁''b''와 ''a'' − ''r''₂''b''의 곱을 계산하여 '''Z'''[''r''₁]와 '''Z'''[''r''₂]에서 제곱근을 구한다. 이 제곱근은 일반적으로 대수적 수로 표현된다.

5. 결과 도출: ''m''은 ''f''와 ''g'' 모두의 근 mod ''n''이므로, 링 '''Z'''[''r''₁]와 '''Z'''[''r''₂]에서 링 '''Z'''/''n'''''Z''' (정수 modulo ''n'')로의 준동형 사상이 존재한다. 이 준동형 사상을 이용하여 각 제곱근을 정수 표현으로 매핑한다. 이를 통해 ''x''² ≡ ''y''² (mod ''n'')''를 만족하는 두 정수 ''x''와 ''y''를 얻을 수 있으며, ''x'' − ''y''와 ''n''의 최대공약수를 계산하여 ''n''의 인수를 찾는다.

3. 1. 대수적 수체

\mathbb Q

(유리수)에 대한 k차 다항식 f가 있고, r이 f의 복소수 근이라고 가정하자. 그러면 f(r) = 0이며, 이 식을 변형하여 r^k를 r의 k 미만의 거듭제곱의 선형 결합으로 표현할 수 있다. 이 방정식은 지수가 e ≥ k 인 r의 거듭제곱을 제거하는 데 사용될 수 있다. 예를 들어, f(x) = x² + 1이고 r이 허수 단위 i이면, i² + 1 = 0 또는 i² = -1이다. 이를 통해 복소수 곱을 정의할 수 있다.

:

(a+bi)(c+di) = ac + (ad+bc)i + (bd)i^2 = (ac - bd) + (ad+bc)i.

일반적으로, 이는 직접적으로 대수적 수체

\mathbb Q[r]

로 이어진다. 이 수체는 다음으로 주어진 복소수의 집합으로 정의될 수 있다.

:

a_{k-1}r^{k-1} + \cdots + a_1 r^1 + a_0 r^0, \text{ where } a_0,\ldots,a_{k-1} \in \mathbb Q.

이러한 값 두 개의 곱은 다항식의 곱을 취한 다음, 위에서 설명한 대로 지수가 e ≥ k인 r의 거듭제곱을 줄여 동일한 형식의 값을 생성하여 계산할 수 있다. 이 체가 실제로 k차원이 되고 더 작은 체로 축소되지 않도록 하려면 f가 유리수에 대한 기약 다항식이면 충분하다. 마찬가지로, 정수환

\mathbb O_{\mathbb Q[r]}

을

\mathbb Q[r]

의 부분 집합으로 정의할 수 있는데, 이 부분 집합은 정수 계수를 갖는 모닉 다항식의 근이다. 어떤 경우에는 이 정수환이 환

\mathbb Z[r]

과 동일하다. 그러나 많은 예외가 있다.^[2]

3. 2. 다항식 선택

일반 숫자체 체(GNFS) 알고리즘의 성능은 적절한 다항식을 선택하는 데 크게 좌우된다. 좋은 다항식을 찾는 것은 알고리즘에서 중요한 단계이다.

GNFS에서는 작은 차수 ''d''와 ''e''를 갖는 두 개의 다항식 ''f''(''x'')와 ''g''(''x'')를 선택한다. 이 다항식들은 정수 계수를 가지며, 유리수 상에서 기약 다항식이어야 하고, mod ''n''으로 해석될 때 공통 정수 근 ''m''을 가져야 한다.

이러한 다항식을 선택하는 최적의 방법은 아직 알려져 있지 않다. 한 가지 간단한 방법은 다항식의 차수 ''d''를 정하고, ''n''^1/''d'' 차수의 여러 다른 ''m''에 대해 base ''m''에서의 ''n''의 확장을 고려하는 것이다. 이때, −''m'' 과 ''m'' 사이의 숫자를 허용하여 계수가 가장 작은 다항식을 ''f''(''x'')로, ''x'' − ''m''을 ''g''(''x'')로 선택한다.

하지만 이 방법은 많은 실제 상황에서 최적이 아니므로, 머피와 브렌트, 클라인융의 방법 등 더 나은 방법들이 개발되었다.

3. 2. 1. 머피와 브렌트의 방법

다항식 선택은 알고리즘의 나머지 단계를 완료하는 시간에 극적으로 영향을 미칠 수 있다. 위에 표시된 내용을 기반으로 다항식을 선택하는 방법은 많은 실제 상황에서 최적이 아니며, 더 나은 방법의 개발로 이어진다.

그러한 방법 중 하나는 머피와 브렌트에 의해 제안되었다.^[3] 그들은 작은 소수 모듈로의 근의 존재와 체질 영역에서 다항식이 갖는 평균값을 기반으로 다항식에 대한 두 부분 점수를 도입했다.

3. 2. 2. 클라인융의 방법

보고된 최상의 결과^[13]는 토르스텐 클라인중의 방법^[14]에 의해 달성되었다. 이 방법은 g(x) = ax + b^영어로 만들 수 있다. 이 방법은 2d^영어를 법으로 하는 1과 합동인 작은 소인수로 구성되는 a^영어 및 최고차 계수가 60으로 나누어 떨어지는 f^영어를 검색한다.^[5]

3. 3. 체질 (Sieving)

체질(sieving)은 작은 차수를 갖는 두 개의 다항식 ''f''(''x'')와 ''g''(''x'')를 선택하는 것에서 시작한다. 이 다항식들은 정수 계수를 가지며, 유리수 상에서 기약 다항식이고, mod ''n''에서 공통 정수 근 ''m''을 갖는다. 이러한 다항식을 선택하는 최적의 방법은 아직 알려져 있지 않다. 한 가지 간단한 방법은 다항식의 차수 ''d''를 정하고, ''n''^1/''d'' 차수의 여러 ''m''에 대해 base ''m''에서의 ''n''의 확장을 고려하여( −''m''과 ''m'' 사이의 숫자를 허용), 가장 작은 계수를 갖는 다항식을 ''f''(''x'')로, ''x'' − ''m''을 ''g''(''x'')로 선택하는 것이다.

다음으로, 수체 링 '''Z'''[''r''₁]와 '''Z'''[''r''₂]를 고려한다. 여기서 ''r''₁과 ''r''₂는 각각 다항식 ''f''와 ''g''의 근이다. 목표는 ''r'' = ''b''^''d''·''f''(''a''/''b'')와 ''s'' = ''b''^''e''·''g''(''a''/''b'')가 선택된 소수 기반에 대해 동시에 smooth number가 되게 하는 정수 ''a''와 ''b'' 값을 찾는 것이다. ''a''와 ''b''가 작으면 ''r''과 ''s''도 작아져서 (''m'' 크기 정도) 동시에 매끄러울 가능성이 높아진다.

이러한 검색에 현재 가장 잘 알려진 방법은 lattice sieving이다. 좋은 결과를 얻으려면 큰 인자 기반을 사용해야 한다. 충분한 쌍을 찾은 후에는, 가우스 소거법을 사용하여 특정 ''r''과 해당 ''s''의 곱이 동시에 제곱수가 되도록 할 수 있다.

''m''은 ''f''와 ''g'' 모두의 근 mod ''n''이므로, 링 '''Z'''[''r''₁]와 '''Z'''[''r''₂]에서 링 '''Z'''/''n'''''Z''' (정수 modulo ''n'')로의 준동형 사상이 존재한다. 이 준동형 사상은 ''r''₁과 ''r''₂를 ''m''에 매핑하고, 각 "제곱근"을 정수 표현으로 매핑한다. 이를 통해 ''x''² − ''y''²가 ''n''으로 나누어지는 두 수 ''x''와 ''y''를 찾을 수 있고, 최소 1/2의 확률로 ''n''과 ''x'' − ''y''의 최대공약수를 계산하여 ''n''의 인수를 얻을 수 있다.

3. 4. 선형 대수

체질 과정에서 얻은 정보를 이용하여 선형 대수 문제를 해결한다. 이 단계에서는 가우스 소거법을 사용할 수 있지만, 최적의 실행 시간을 얻기 위해 블록 란초스 알고리즘이나 블록 비데만 알고리즘과 같은 희소 행렬 솔버 알고리즘을 사용한다.^[3]

충분히 많은 쌍을 찾으면, 가우스 소거법을 이용하여 특정 ''r''과 해당 ''s''의 곱을 동시에 제곱수로 만들 수 있다. 다만, 각 곱은 수체에서의 제곱수의 노름이라는 더 강한 조건이 필요하지만, 이 조건도 만족시킬 수 있다. 각 ''r''은 ''a'' − ''r''₁''b''의 노름이므로, 해당 소인수 ''a'' − ''r''₁''b''의 곱은 '''Z'''[''r''₁]에서 제곱수가 되며, "제곱근"을 결정할 수 있다. 이 "제곱근"은 일반적으로 무리수인 대수적 수로 표현된다. 마찬가지로, 소인자 ''a'' − ''r''₂''b''의 곱은 '''Z'''[''r''₂]에서 제곱수가 되며, "제곱근"도 계산할 수 있다.^[3]

3. 5. 제곱근 계산

가우스 소거법을 사용하여 특정 ''r''과 해당 ''s''의 곱이 동시에 제곱수가 되도록 할 수 있다. 이를 위해서는 각 곱이 수체에서 제곱수의 노름이어야 한다는 더 강력한 조건이 필요하지만, 이 조건도 만족시킬 수 있다. 각 ''r''은 ''a'' − ''r''₁''b''의 노름이므로, 해당 인자 ''a'' − ''r''₁''b''의 곱은 '''Z'''[''r''₁]에서 제곱수가 되며, "제곱근"은 ('''Z'''[''r''₁]에서 알려진 인자의 곱으로) 결정할 수 있다. 이는 일반적으로 무리수인 대수적 수로 표현된다. 마찬가지로, 인자 ''a'' − ''r''₂''b''의 곱은 '''Z'''[''r''₂]에서 제곱수가 되며, "제곱근"도 계산할 수 있다.^[2] 가우스 소거법을 사용하면 알고리즘의 최적 실행 시간이 나오지 않으므로, 블록 란초스 알고리즘 또는 블록 비데만 알고리즘과 같은 희소 행렬 해결 알고리즘이 사용된다.^[2]

4. 구현

GNFS 알고리즘은 실제로 구현하기 복잡하며, 여러 단계와 최적화 기법이 필요하다.

일부 구현은 특정 소규모 숫자 클래스에 중점을 두는데, 이는 커닝햄 프로젝트에서 사용되는 특수 숫자 밭 체 기술로 알려져 있다.^[15] NFSNET은 2002년부터^[15] 2007년까지^[16] 인터넷 자원봉사자들의 분산 컴퓨팅을 활용한 프로젝트로, 영국의 폴 레이랜드와 텍사스의 리처드 와커바스가 참여했다.^[17]

2007년까지 표준 구현은 네덜란드의 CWI에서 개발 및 배포한 소프트웨어 모음이었으며, 비교적 제한적인 라이선스로만 이용 가능했다. 같은 해, 제이슨 파파도풀로스는 퍼블릭 도메인에 있는 msieve의 일부로 최종 처리를 더 빠르게 구현했다. CWI와 msieve 구현 모두 충분히 빠른 통신을 할 수 있는 클러스터 내 여러 노드로 분산할 수 있는 기능을 갖추고 있다.

다항식 선택은 일반적으로 Kleinjung이 작성한 GPL 소프트웨어 또는 msieve에 의해 수행되며, 격자 체는 Franke와 Kleinjung이 작성한 GPL 소프트웨어에 의해 수행된다. 이들은 GGNFS로 배포된다.

4. 1. 주요 구현체

다음은 널리 사용되는 GNFS 구현체들이다.

CWI: 2007년까지 최고 수준의 구현체는 네덜란드의 CWI에서 개발한 소프트웨어 모음이었으나, 제한적인 라이선스로만 사용할 수 있었다.^[6]
msieve: 2007년 제이슨 파파도풀로스가 개발한 공개 소프트웨어로, 최종 처리 속도가 빠르다.^[6] CWI와 msieve 구현체는 모두 빠른 연결을 가진 클러스터의 여러 노드에 분산될 수 있다.^[6]
GGNFS: Kleinjung이 작성한 GPL 소프트웨어(다항식 선택)와 Franke와 Kleinjung이 작성한 GPL 소프트웨어(격자 체)를 포함한다.
CADO-NFS:
factor by gnfs:
kmGNFS:

일부 구현은 커닝햄 프로젝트에서 사용되는 특수 숫자 밭 체 기술에 중점을 둔다.^[15] NFSNET은 2002년부터^[15] 2007년까지^[16] 인터넷 자원봉사자들의 분산 컴퓨팅을 활용한 프로젝트로, 영국의 폴 레이랜드와 텍사스의 리처드 와커바스가 참여했다.^[17]

4. 2. 분산 컴퓨팅

NFSNET은 2002년부터^[6] 최소 2007년까지 운영된 프로젝트로, 인터넷에서 자원봉사자들의 분산 컴퓨팅을 활용했다.^[7] 이 프로젝트에는 영국의 폴 레이랜드와 텍사스 출신의 리처드 와커바스(Richard Wackerbarth)가 참여했다.^[8] NFS@Home은 일반 숫자 밭 체(GNFS)를 이용한 분산 컴퓨팅 프로젝트 중 하나이다.

참조

_[1] 뉴스 A Tale of Two Sieves https://www.ams.org/[...] 1996-12
_[2] 서적 Algebraic Numbers Wiley-Interscience
_[3] 간행물 On quadratic polynomials for the number field sieve http://maths-people.[...] 1998
_[4] 간행물 On RSA 200 and larger projects http://www.hyperelli[...]
_[5] 논문 On polynomial selection for the general number field sieve https://www.ams.org/[...] 2007-12-13
_[6] 웹사이트 NFSNET: the first year http://homepages.cwi[...] 2011-08-09
_[7] 웹사이트 Welcome to NFSNET http://www.nfsnet.or[...] 2011-08-09
_[8] 웹사이트 About NFSNET http://www.nfsnet.or[...] 2011-08-09
_[9] 논문 近年の素因数分解について https://doi.org/10.1[...] 電子情報通信学会 2008
_[10] 뉴스 A Tale of Two Sieves https://www.ams.org/[...] 1996-12
_[11] 서적 Algebraic Numbers Wiley-Interscience
_[12] 논문 On quadratic polynomials for the issue field sieve http://digitalcollec[...] The Australian National University
_[13] 간행물 On RSA 200 and larger projects http://www.hyperelli[...]
_[14] 논문 On polynomial selection for the general number field sieve https://www.ams.org/[...] 2007-12-13
_[15] 웹사이트 NFSNET: the first year http://homepages.cwi[...] 2011-08-09
_[16] 웹사이트 Welcome to NFSNET http://www.nfsnet.or[...] 2011-08-09
_[17] 웹사이트 About NFSNET http://www.nfsnet.or[...] 2011-08-09

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

문의하기 : help@durumis.com