특수장 체

수학의 한 분야인 수론에서 특수수 분야 체(SNFS)는 특수 목적 정수 인자화 알고리즘이다. 일반수 필드 체(GNFS)는 여기서 파생되었다.

특수수 필드 체는 r과 s가 작은 r^e ± s 형식의 정수(예: 메르센 수)에 효율적이다.

경험적으로, 정수 $n$ $n$ 을(를) 인수하기 위한 복잡성은 다음과 $n$ 같다.^[1]

\exp \left(\왼쪽(1+o(1)\오른쪽)\left\tfrac {32}{9}\log n\right)^{1/3}\reft(\log \log n\오른쪽)^{2/3}\rig)=L_{n}\왼쪽[1/3,(32/9)^{1/3}\오른쪽]

O와 L-notation으로.

SNFS는 NFSNet(자원봉사자 분산 컴퓨팅 노력), NFS@Home 등에 의해 커닝햄 프로젝트의 숫자를 고려하는 데 광범위하게 사용되어 왔으며, 한동안 정수 인자화에 대한 기록은 SNFS에 의해 인수되었다.

방법 개요

SNFS는 훨씬 단순한 이성 체와 유사한 아이디어를 바탕으로 한다. 특히 독자들은 SNFS를 다루기 전에 이성 체에 대해 먼저 읽는 것이 도움이 될 수 있다.

SNFS는 다음과 같이 작동한다. n을 우리가 고려하고자 하는 정수가 되게 하라. 합리적 체에서와 같이 SNFS는 두 단계로 나눌 수 있다.

첫째, Z/nZ 요소의 인자 베이스 사이에서 많은 수의 곱셈 관계를 찾아, 인자 베이스에 있는 원소의 수보다 곱셈 관계의 수가 더 많다.
둘째, 이러한 관계의 하위 집합을 모든 지수가 균등하게 하여 a²≡b²(mod n)형식의 합치를 초래하는 방법으로 곱한다. 이는 즉시 n: n=gcd(a+b,n)×gcd(a-b,n)의 인자로 이어진다. 제대로만 된다면 적어도 한 가지 그러한 요소화는 비교가 되지 않을 것이 거의 확실하다.

두 번째 단계는 이성 체의 경우와 동일하며, 직선적인 선형 대수 문제다. 그러나 첫 번째 단계는 숫자 분야를 활용하여 합리적인 체와 다른, 보다 효율적인 방법으로 이루어진다.

방법내역

n을 우리가 고려하고자 하는 정수가 되게 하라. 우리는 정수 계수가 있는 수정 불가능한 다항식 f를 선택하고, f(m) (0 (mod n)과 같은 정수 m을 선택한다(우리는 그것들이 어떻게 선택되는지를 다음 절에서 설명하겠다). α를 f의 뿌리가 되게 하라; 그러면 우리는 고리 Z[α]를 형성할 수 있다. Z[α]에서 Z/nZ까지 α를 m로 매핑하는 독특한 고리 동형성이 있다. 간단히 말해서, Z[α]가 고유한 요인화 영역이라고 가정해 봅시다. 알고리즘은 그렇지 않을 때 작동할 수 있도록 수정될 수 있지만, 그 다음에는 약간의 추가적인 합병증이 있다.

다음으로, 우리는 두 개의 평행인자 베이스를 설정했는데, 하나는 Z[α]이고 다른 하나는 Z[α]이다. Z[α]의 하나는 Z[α]의 모든 주요 이상으로 구성되며, 그 표준은 선택된 값 $N_{\max }$ $N_{\max }$ ${\$ 에 의해 제한된다 $N_{\max }$ 합리적인 체의 경우와 마찬가지로 Z의 인자 베이스는 다른 경계까지의 모든 주요 정수로 구성된다.

그런 다음 다음과 같은 비교적 프라임 쌍의 정수(a,b)를 검색한다.

a+bm은 Z의 인자 베이스에 관해서 부드럽다(즉, 인자 베이스의 원소들의 산물이다).
a+bα는 Z[α]의 인자 베이스와 관련하여 부드럽다. 우리가 인자 베이스를 선택한 방법을 고려할 때, 이것은 a+bα가 $N_{\max }$ $N_{\max }$ ${\$ 보다 작은 소수만으로 분할되는 규범과 같다 $N_{\max }$

이 쌍들은 에라토스테네스의 체와 유사한 체를 통해 발견된다. 이것은 "숫자 필드 체"라는 이름에 동기를 부여한다.

그러한 각 쌍에 대해 a+bα의 인자화에 링 동형성 φ을 적용할 수 있으며, Z에서 Z/nZ까지의 표준 링 동형성을 a+bm의 인자화에 적용할 수 있다. 이러한 요소들을 동등하게 설정하면 Z/nZ의 더 큰 요인 베이스의 요소들 사이에 승법적인 관계가 형성되며, 만약 우리가 충분한 쌍을 발견한다면 우리는 위에서 설명한 바와 같이 관계와 요인 n을 결합하는 것을 진행할 수 있다.

파라미터 선택

Not every number is an appropriate choice for the SNFS: you need to know in advance a polynomial f of appropriate degree (the optimal degree is conjectured to be $\left(3{\frac {\log N}{\log \log N}}\right)^{1/3}$ , which is 4, 5, or 6 for the sizes of N currently feasible to 계수)가 작으며 $f(x)\equiv 0{\pmod {N}}$ $f(x)\equiv 0{\pmod {N}}$ ) $f(x)\equiv 0{\pmod {N}}$ 0 $f(x)\equiv 0{\pmod {N}}$ $f(x)\equiv 0{\pmod {N}}$ ) ${\$ 과 같은 값 x를 인수할 수 있다. 여기서 $f(x)\equiv 0{\pmod {N}}$ N은 인수할 수입니다. 추가 조건이 있다: x는 N $N^{1/d}$ / $N^{1/d}$ ${\$ d $디스플레이$ 스타일 $N^{1/d}$ 이하의 a 및 b에 대해 $ax+b\equiv 0{\pmod {N}}$ $ax+b\equiv 0{\pmod {N}}$ + b $ax+b\equiv 0{\pmod {N}}$ $($ $ax+b\equiv 0{\pmod {N}}$ ) $displaystyle ax+b\equiv 0{\pmod{N}}}}$ 을 충족해야 한다 $N^{1/d}$

One set of numbers for which such polynomials exist are the $a^{b}\pm 1$ numbers from the Cunningham tables; for example, when NFSNET factored 3^479+1, they used the polynomial x^6+3 with x=3^80, since (3^80)^6+3 = 3^480+3, and ${\displaystyle 3^{480}+3\equiv 0{\pmod$ ${3^{479}+1}}}$ .

피보나치 수나 루카스 수처럼 선형 재귀에 의해 정의되는 숫자도 SNFS 다항식을 가지고 있지만, 이것들을 구성하기는 조금 더 어렵다. For example, $F_{709}$ has polynomial $n^{5}+10n^{3}+10n^{2}+10n+3$ , and the value of x satisfies $F_{142}x-F_{141}=0$ .^[2]

If you already know some factors of a large SNFS-number, you can do the SNFS calculation modulo the remaining part; for the NFSNET example above, 3^479+1 = (4*158071*7167757*7759574882776161031) times a 197-digit composite number (the small factors were removed by ECM), and the SNFS was performed modulo the 197-digit number. SNFS가 요구하는 관계의 수는 여전히 큰 숫자의 크기에 따라 다르지만, 개별 계산은 작은 숫자보다 더 빠르다.

알고리즘의 한계

위에서 언급한 바와 같이 이 알고리즘은 r^e±s형식의 숫자에 대해 r과 s의 비교적 작은 경우에 매우 효율적이다. 계수가 작은 다항식으로 표현될 수 있는 정수에 대해서도 효율적이다. 여기에는 보다 일반적인 형태의 ar^e±b의^f 정수와 이항 표현으로 해밍 가중치가 낮은 많은 정수의 정수가 포함된다. 그 이유는 다음과 같다. Number 필드 체는 두 개의 다른 필드에서 체를 수행한다. 첫번째 분야는 대개 이성적이다. 두 번째는 고등학위 분야다. 알고리즘의 효율성은 이들 분야에서 특정 요소의 규범에 따라 크게 좌우된다. 정수를 계수가 작은 다항식으로 나타낼 수 있는 경우, 정수를 일반 다항식으로 나타낼 때 발생하는 규범보다 훨씬 작다. 그 이유는 일반 다항식은 계수가 훨씬 더 크고, 규범도 그에 상응하여 더 클 것이기 때문이다. 알고리즘은 이러한 규범들을 고정된 소수보다 더 많이 고려하려고 시도한다. 규범이 더 작을 때, 이 숫자들은 더 고려될 가능성이 있다.

참고 항목

일반수 필드 체

참조

^ Pomerance, Carl (December 1996), "A Tale of Two Sieves" (PDF), Notices of the AMS, vol. 43, no. 12, pp. 1473–1485
^ Franke, Jens. "Installation notes for ggnfs-lasieve4". MIT Massachusetts Institute of Technology.

추가 읽기

Byrnes, Steven (May 18, 2005), "The Number Field Sieve" (PDF), Math 129
Lenstra, A. K.; Lenstra, H. W., Jr.; Manasse, M. S. & Pollard, J. M. (1993), "The Factorization of the Ninth Fermat Number", Mathematics of Computation, 61 (203): 319–349, Bibcode:1993MaCom..61..319L, doi:10.1090/S0025-5718-1993-1182953-4
Lenstra, A. K.; Lenstra, H. W., Jr., eds. (1993), The Development of the Number Field Sieve, Lecture Notes in Mathematics, vol. 1554, New York: Springer-Verlag, ISBN 978-3-540-57013-4
Silverman, Robert D. (2007), "Optimal Parameterization of SNFS", Journal of Mathematical Cryptology, 1 (2): 105–124, CiteSeerX 10.1.1.12.2975, doi:10.1515/JMC.2007.007

[1] Pomerance, Carl (December 1996), "A Tale of Two Sieves" (PDF), Notices of the AMS, vol. 43, no. 12, pp. 1473–1485

[2] Franke, Jens. "Installation notes for ggnfs-lasieve4". MIT Massachusetts Institute of Technology.

[1]

[2]

v t 수이론적 알고리즘
원시성 검정	AKS APR 바일리-PSW 타원곡선 포클링턴 페르마 루카스 루카스-레머 루카스-레머-리젤 프로트의 정리 페핀스 이차적 프로베니우스 솔로베이-스트라센 밀러-라빈
프라임 생성	앳킨의 체 에라토스테네스의 체 순다람의 체 휠 인자화
정수 인자화	지속분수(CFRAC) 딕슨스 Lenstra 타원 곡선(ECM) 오일러즈 폴라드 호 p − 1 p + 1 2차 체(QS) 일반수 필드 체(GNFS) 특수수 필드 체(SNFS) 이성 체 페르마츠 샨크스의 사각형 재판분할 쇼르스
곱하기	고대 이집트인 긴 카라츠바 툼-쿡 sch나게-스트라센 총통의
유클리드 주 나누기	이진수 청킹 푸리에 골드슈미트 뉴턴-래프슨 긴 짧다 SRT
이산 로그	베이비 스텝 거인 스텝 폴라드 로 폴라드 캥거루 포흘리그-헬먼 지수 미적분학 기능장 체
최대공통점	이진수 유클리드 주 확장유클리드 르메르스
모듈형 제곱근	시폴라 포클링턴스 토넬리-상크스 베를레캄프 쿠네르스
기타 알고리즘	차크라발라 코르나키아 제곱에 의한 지수화 정수 제곱근 정수 관계(LL; KZ) 모듈형 지수 몽고메리 환원 슈프
이탤릭체는 알고리즘이 특수형태의 숫자에 대한 것임을 나타낸다.

Search