일반수 필드 체

General number field sieve

수 이론에서 일반수 필드 체(GNFS)는 10보다100 큰 정수를 인수하는 것으로 알려진 가장 효율적인 고전 알고리즘이다. 경험적으로, 정수 n을 인수하기 위한 복잡성( bitslog n2⌋ + 1비트로 구성)은 형태다.

(L-notation에서), 여기서 ln은 자연 로그다.[1] 그것은 특수장 체의 일반화인데, 후자는 특정 특수의 숫자만 인자할 수 있는 반면, 일반수장 체는 소수권력(뿌리잡아서 인자로 삼기에는 사소한 것)을 제외한 어떤 숫자도 인자할 수 있다.

수 체(특수 체와 일반 체)의 원리는 보다 단순한 이성 체나 2차 체에 대한 개선으로 이해할 수 있다. 그러한 알고리즘을 사용하여 큰 숫자 n을 인자화할 때, 순서 n의1/2 부드러운 숫자(즉, 소수 인자를 가진 숫자)를 검색할 필요가 있다. 이러한 값의 크기는 n의 크기가 지수적이다(아래 참조). 반면에 일반수 필드 체는 n의 크기에서 부차적인 부드러운 숫자를 찾아낸다. 이 숫자는 더 작기 때문에 이전 알고리즘에서 검사한 숫자보다 매끄러울 가능성이 높다. 이것이 숫자 필드 체의 효율성의 비결이다. 이러한 속도 증가를 달성하기 위해서는 수 필드 체가 수 필드에서 연산 및 인자화를 수행해야 한다. 이것은 단순한 이성 체에 비해 알고리즘의 많은 복잡한 측면을 초래한다.

알고리즘에 대한 입력의 크기는 로그2 n 또는 n의 이진 표현에 있는 비트 수입니다. 상수 c에 대한 nc 순서의 모든 요소는 로그 n에서 지수적이다. 숫자 필드 체의 실행 시간은 초다항식이지만 입력 크기에서는 부차적이다.

수 필드

주요 기사: 숫자 필드

f가 Q(합리적 수)에 대한 k-di 다항식이고 r이 f의 복잡한 뿌리라고 가정하자. 그런 다음, f(r) = 0으로, r을k k 이하의 힘의 선형 결합으로 표현하도록 재배열할 수 있다. 이 방정식은 지수 e ≥ k로 r의 힘을 감소시키는 데 사용될 수 있다. 예를 들어 f(x) = x + 1이고2 r이 가상 단위 i인 경우 i2 + 1 = 0 또는 i = -1이다2. 이를 통해 복잡한 제품을 정의할 수 있다.

일반적으로 이는 대수적 숫자 필드 Q[r]로 직접 연결되며, 이는 다음과 같이 주어지는 복잡한 숫자의 집합으로 정의할 수 있다.

그러한 두 값의 산출물은 제품을 다항식으로 취하여 계산할 수 있으며, 위에서 설명한 바와 같이 지수 e ≥ k로 r의 힘을 감소시켜 동일한 형태로 값을 산출할 수 있다. 이 필드가 실제로 k-차원이고 더 작은 필드로 무너지지 않도록 하기 위해서는 f가 합리성에 대한 불가해한 다항식이라는 것으로 충분하다. 마찬가지로 정수 O의Q[r] 링은 정수 계수를 갖는 단항식의 뿌리인 Q[r]의 부분집합으로 정의할 수 있다. 어떤 경우에는 이 정수 링이 Z[r] 링과 맞먹는 경우도 있다. 단, d가 1모듈로 4일 때 Q[√]와 같이 예외가 많다.[2]

방법

d와 e의 작은 두 개의 다항식 f(x)와 g(x)를 선택하는데, 이 중 정수 계수는 이성보다 판독할 수 없고, mod n을 해석할 때 공통 정수근 m을 갖는다. 이러한 다항식을 선택하기 위한 최적의 전략은 알려지지 않았다. 한 가지 간단한 방법은 다항식의 d를 선택하고, n의 다른1/d m에 대해 n in base m( -m과 m 사이의 허용 자릿수)의 확장을 고려하며, f(x)를 계수가 가장 작은 다항식으로, g(x)를 x - m로 선택하는 것이다.

필드 링 숫자12 Z[r]와 Z[r2]를 고려하십시오. 여기서 r과1 r은 다항식 f와 g의 루트입니다. f는 정수 계수를 가진 도 d이기 때문에 a와 b가 정수라면 bd·f(a/b)가 될 것이고, 이를 r이라고 부른다. 마찬가지로 s = be·g(a/b)는 정수다. 목표는 선택한 소수점 기준으로 r과 s를 동시에 부드럽게 만드는 a와 b의 정수 값을 찾는 것이다. a와 b가 작으면 r과 s도 m 크기 정도로 작을 것이고, 동시에 부드러워질 수 있는 더 좋은 기회를 갖게 된다. 이 검색에 대해 현재 가장 잘 알려진 접근법은 격자 체이빙이다. 허용 가능한 수율을 얻으려면 큰 요인 기반을 사용할 필요가 있다.

그러한 쌍을 충분히 가지면 가우스 제거를 사용하여 특정 r과 해당 s의 곱을 동시에 제곱할 수 있다. 조금 더 강한 조건이 필요하다. 그것들이 우리의 수 분야에서는 정사각형의 규범이지만, 그 조건은 이 방법으로도 달성될 수 있다. 각 r은 a - rb의1 규범이며, 따라서 a - rb의1 산물은 Z[r]의 제곱이고, "제곱근1"은 (Z[r1]의 알려진 인자의 산물로) 결정할 수 있다. 즉, 일반적으로 비합리적인 대수적 숫자로 표현될 것이다. 마찬가지로, a - rb2 인자의 곱은 Z[r2]의 제곱이고, "제곱근"도 계산할 수 있다. 가우스 제거를 사용하면 알고리즘의 최적 실행 시간이 주어지지 않는다는 점을 유념해야 한다. 대신 Block Lanczos 또는 Block Wedemann과 같은 희소성 매트릭스 해결 알고리즘이 사용된다.

m은 f[r1]와 g mod n의 루트이기 때문에, r과12 r을 m에 매핑하는 링 Z[r]와 Z[r2]에서 링 Z/nZ(정수 modulo n)까지 동형성이 있으며, 이러한 동형성들은 각각의 "제곱근"(일반적으로 합리적인 숫자로 표현되지 않음)을 정수 대표에 매핑할 것이다. 이제 a -mb mod n 인자의 산물은 두 가지 방법으로 제곱으로 얻을 수 있다. 각 동형성마다 하나씩이다. 따라서 두 개의 숫자 x와 y를 찾을 수 있으며, x2 - y는2 n으로 분할하고, 다시 최소한 1/2의 확률로 우리는 n과 x - y의 가장 큰 공통점을 찾음으로써 n의 인자를 얻을 수 있다.

다항식 선택 개선

다항식의 선택은 알고리즘의 나머지 부분을 완료하는 시간에 극적으로 영향을 미칠 수 있다. 상기와 같이 base m에서 n의 확장에 근거한 다항식을 선택하는 방법은 많은 실제 상황에서 차선책으로서, 보다 나은 방법의 개발로 이어진다.

그러한 방법 중 하나는 머피와 브렌트에 의해 제안되었다;[3] 그들은 뿌리 모듈로 작은 프리임의 존재와 다항식이 체이빙 영역을 차지하는 평균 값에 기초하여 다항식의 2부 점수를 도입한다.

가장 잘 보고된 결과는[4] g(x) = 도끼 + b를 허용하는 [5]Thorsten Kleinjung의 방법과 1 modulo 2d와 60으로 구분되는 f의 선행 계수를 합친 작은 주요 인자로 구성된 검색에 의해 달성되었다.

구현

일부 구현에서는 특정 소형의 숫자에 초점을 맞춘다. 이것들은 커닝햄 프로젝트에 사용되는 것과 같은 특별한 숫자 필드 체 기법이라고 알려져 있다. NFSNET이라는 프로젝트는 2002년부터[6] 적어도 2007년까지 실행되었다. 인터넷 상에서 자원봉사자 분산 컴퓨팅을 이용했다.[7] 영국의 폴 레이랜드와 텍사스의 리처드 와커바스가 연루되었다.[8]

2007년까지 금본위 구현은 네덜란드의 CWI가 개발·보급하는 소프트웨어 모음이었는데, 비교적 제한적인 면허에 의해서만 이용이 가능했다.[citation needed] 2007년에 제이슨 파파도풀로스는 공공영역에 있는 misieve의 일부로 최종 처리의 더 빠른 구현을 개발했다. 두 구현 모두 충분히 빠른 인터커넥트를 통해 클러스터의 여러 노드 간에 분산되는 기능을 특징으로 한다.

다항 선택은 일반적으로 클라인정이 작성한 GPL 소프트웨어 또는 Franke와 클라인정이 작성한 GPL 소프트웨어에 의해 수행되며, 이는 GGNFS에 배포된다.

참고 항목

메모들

  1. ^ Pomerance, Carl (December 1996). "A Tale of Two Sieves" (PDF). Notices of the AMS. Vol. 43, no. 12. pp. 1473–1485.
  2. ^ Ribenboim, Paulo (1972). Algebraic Numbers. Wiley-Interscience. ISBN 978-0-471-71804-8.
  3. ^ Murphy, B.; Brent, R. P. (1998), "On quadratic polynomials for the number field sieve", Australian Computer Science Communications, 20: 199–213
  4. ^ Franke, Jens (2006), On RSA 200 and larger projects (PDF)
  5. ^ Kleinjung, Thorsten (October 2006). "On polynomial selection for the general number field sieve" (PDF). Mathematics of Computation. 75 (256): 2037–2047. doi:10.1090/S0025-5718-06-01870-9. Retrieved 2007-12-13.
  6. ^ Paul Leyland (December 12, 2003). "NFSNET: the first year". Presentation at EIDMA-CWI Workshop on Factoring Large Numbers. Retrieved August 9, 2011.
  7. ^ "Welcome to NFSNET". April 23, 2007. Archived from the original on October 22, 2007. Retrieved August 9, 2011.
  8. ^ "About NFSNET". Archived from the original on May 9, 2008. Retrieved August 9, 2011.

참조

  • 매튜 브릭스: 일반수 필드 체에 대한 소개, 1998