Jump to content

Integer factorization

This is a fully translated article. Click here for more information.
From DawoumWiki, the free Mathematics self-learning
Original article: w:Integer factorization
"Prime decomposition" redirects here. For the prime decomposition theorem for 3-manifolds, see Prime decomposition (3-manifold).
Unsolved problem in computer science:

Can integer factorization be solved in polynomial time on a classical computer?

(more unsolved problems in computer science)

숫자 이론(number theory)에서, 정수 인수분해(integer factorization)는 합성수(composite number)를 더 작은 정수의 곱(product)으로의 분해입니다. 만약 이들 인수가 소수(prime number)로 더 제한되면 그 과정은 소수 인수분해(prime factorization)라고 불립니다.

숫자가 충분하게 클 때, 효율적인, 비-양자(non-quantum) 정수 인수분해(factorization) 알고리듬(algorithm)이 알려져 있지 않습니다. 어쨌든, 효율적인 알고리듬이 존재하지 않는다는 것이 입증되지 않았습니다. 이 문제의 예상되는 어려움(difficulty)은 RSA와 같은 암호화(cryptography)에서 널리 사용되는 알고리듬의 핵심에 있습니다. 수학(mathematics)과 컴퓨터 과학(computer science)의 많은 영역이 타원 곡선(elliptic curve), 대수적 숫자 이론(algebraic number theory), 및 양자 컴퓨팅(quantum computing)을 포함하여 이 문제를 다루게 되어 왔습니다.

2019년에, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, 및 Paul Zimmermann은 근사적으로 900 코어-년 컴퓨팅 파워를 활용하여 240-자릿수 (795-비트) 숫자 (RSA-240)를 인수화했습니다.[1] 연구원들은 1024-비트 RSA 모듈러스가 약 500배 더 오래 걸릴 것으로 추정했습니다.[2]

주어진 길이의 모든 숫자가 똑같이 인수화하기 어려운 것은 아닙니다. 이들 문제의 가장 어려운 인스턴스 (현재 알려진 기술에 대해)는 두 소수의 곱, 반소수(semiprime)입니다. 그것들은 둘 다 큰, 예를 들어 2,000 비트 이상으로 긴, 무작위로 선택되고, 거의 같은 크기일 때 (그러나, 예를 들어, 페르마의 인수분해 방법(Fermat's factorization method)에 의한 효율적인 인수분해를 피하기 위해 너무 가깝지 않을 때), 심지어 가장 빠른 컴퓨터 위에 가장 빠른 소수 인수분해 알고리듬조차 검색을 비실용적으로 만들기에 충분한 시간이 걸릴 수 있습니다; 즉, 인수화되려는 소수의 자릿수가 증가함에 따라, 임의의 컴퓨터에서 인수분해를 수행하기 위해 요구된 연산 수가 급격히 증가합니다.

많은 암호화 프로토콜은 RSA 문제(RSA problem)와 같은 큰 복합 정수를 인수화하는 또는 관련된 문제의 어려움을 기반으로 합니다. 임의적인 정수를 효율적으로 인수화하는 알고리듬은 RSA-기반 공개-키(public-key) 암호화를 불안정하게 렌드링할 것입니다.

Prime decomposition

Prime decomposition of n = 864 as 25 × 33

산술의 기본 정리(fundamental theorem of arithmetic)에 의해, 모든 각 양의 정수는 고유한 소수 인수(prime factor)분해를 가집니다. (관례에 의해, 1은 빈 곱(empty product)입니다.) 정수가 소수인지 여부를 테스트하는 것은 예를 들어 AKS 소수성 테스트(AKS primality test)에 의해 다항식 시간(polynomial time)에 수행될 수 있습니다. 만약 복합수이면, 어쨌든, 다항식 시간 테스트는 인수를 얻기 위한 방법으로의 통찰력을 제공하지 않습니다.

정수 인수분해에 대해 일반적인 알고리듬이 주어지면, 임의의 정수는 이 알고리듬의 반복된 적용에 의해 그것의 구성 소수 인수(prime factor)로 인수화될 수 있습니다. 그 상황은 특수-목적 인수분해 알고리듬과 함께 더 복잡해지며, 그것의 이점은 분해 동안 생성된 인수로 잘 실현되지 않을 수 있거나 전혀 실현되지 않을 수 있습니다. 예를 들어, 만약 p < q가 매우 큰 소수인 n = 171 × p × q이면, 나눗셈 시도(trial division)는 인수 3과 19를 빠르게 생성하지만 다음 인수를 찾기 위해 p 나눗셈을 수행합니다. 대조적인 예제로서, 만약 n이 소수 13729, 1372933, 및 18848997161의 곱이면, 여기서 13729 × 1372933 = 18848997157이며, 페르마의 인수분해 방법은 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle \lceil\sqrt{n}\rceil = 18848997159 } 로 시작할 것이며, 즉시 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\textstyle b = \sqrt{a^2-n} = \sqrt{4} = 2b } 를 산출하고 따라서 인수 a − b = 18848997157와 a + b = 18848997161입니다. 이것들은 각각 합성수와 소수로 쉽게 인식되지만, 페르마의 방법은 합성수를 인수화하기 위해 훨씬 더 오래 걸릴 것인데 왜냐하면 a에 대해 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\textstyle \lceil\sqrt{18848997157}\rceil = 137292 } 의 시작하는 값은 1372933 근처에 없기 때문입니다.

Current state of the art

See also: Integer factorization records

b-비트 숫자 중에서, 기존 알고리듬을 사용하여 실제로 인수화하기 가장 어려운 것은 비슷한 크기의 두 소수의 곱인 숫자입니다. 이러한 이유로, 이들은 암호화 응용에서 사용되는 정수입니다. 2020년 당시까지 인수화되었던 가장 큰 그러한 반소수는 2020년 2월의 RSA-250, 250 십진 자릿수를 갖는 829-비트 숫자였습니다. 전체 계산 시간은 2.1GHz에서 Intel Xeon Gold 6130을 사용한 컴퓨팅의 대략 2700 코어-년였습니다. 모든 최근 인수분해 기록과 마찬가지로, 이 인수분해는 수백 대의 기계에서 실행되는 일반 숫자 필드 체(general number field sieve)의 고도로 최적화된 구현으로 완료되었습니다.

Difficulty and complexity

알고리듬(algorithm)은 다항식 시간(polynomial time)에서 모든 정수를 인수화할 수 있는, 즉 일부 상수 k에 대해 시간 O(bk)에서 b-비트 숫자 n을 인수화할 수 있는 것은 발표된 적이 없습니다. 그러한 알고리듬의 존재하는지 그렇지 않은지 여부는 입증되지 않았지만, 일반적으로 그것들은 존재하지 않고 따라서 문제는 클래스 P에 속하지 않는 것으로 의심되고 있습니다.[3][4] 그 문제는 분명히 클래스 NP에 있지만, 일반적으로 비록 이것이 입증된 적은 없을지라도 그것은 NP-완전(NP-complete)은 아닌 것으로 의심됩니다.[5]

모든 양의 ε에 대해 O((1 + ε)b), 즉 하위-지수(sub-exponential)보다 빠른 출판된 알고리듬이 있습니다. 2021년 3월 12일 당시, 최상의 이론상 점근적 실행 시간을 갖는 알고리듬은 1993년에 처음 발표된 일반 숫자 필드 체 (GNFS)이며,[6] 시간에서 b-비트 숫자 n에서 실행합니다.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle \exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right).}

현재 컴퓨터에 대해, GNFS는 큰 n (약 400 비트 이상)에 대해 최상의 출판된 알고리듬입니다. 양자 컴퓨터(quantum computer)에 대해, 어쨌든, 피터 쇼어(Peter Shor)는 1994년 그것을 다항식 시간에서 해결하는 알고리듬을 발견했습니다. 이것은 만약 양자 계산이 확장-가능해지면 암호화에 중요한 의미를 가질 것입니다. 쇼어의 알고리듬(Shor's algorithm)은 b-비트 숫자 입력에서 오직 O(b3) 시간과 O(b) 공간을 사용합니다. 2001년에, 쇼어의 알고리듬은 7 큐비트를 제공하는 분자에 NMR 기술을 사용함으로써 처음으로 구현되었습니다.[7]

어떤 복잡도 클래스(complexity class)가 정수 인수분해 문제의 결정 버전(decision version)을 포함하고 있는지 정확하게 알려져 있지는 않습니다 (즉: n이 k보다 작은 인수를 가집니까?). 그것은 NP와 co-NP 둘 다에 있는 것으로 알려져 있으며, "예"와 "아니오" 대답 둘 다가 다항식 시간에 검증될 수 있음을 의미합니다. "예"라는 대답은 d ≤ k를 갖는 인수분해 n = d(n/d)를 보여줌으로써 인증될 수 있습니다. "아니오"라는 대답은 n을 모두 k보다 큰 구별되는 소수로의 인수분해를 보여줌으로써 검증될 수 있습니다; 우리는 AKS 소수성 테스트(AKS primality test)를 사용하여 그것들의 소수성을 검증하고, 그런-다음 n을 얻기 위해 그것들을 곱할 수 있습니다. 산술의 기본 정리(fundamental theorem of arithmetic)는 허용될 수 있는 증가하는 소수의 유일한 하나의 가능한 문자열이 있음을 보장하며, 이것은 그 문제가 UP와 co-UP 둘 다에 있음을 보여줍니다.[8] 그것은 쇼어의 알고리듬 때문에 BQP에 있는 것으로 알려져 있습니다.

그 문제는 복잡도 클래스 P, NP-완전, 및 co-NP-완전(co-NP-complete)의 세 가지 모두를 벗어나는 것으로 의심됩니다. 그것은 따라서 NP-중간(NP-intermediate) 복잡도 클래스에 대해 후보입니다. 만약 그것이 NP-완전 또는 co-NP-완전으로 입증될 수 있으면, 이것은 NP = co-NP, 매우 놀라운 결과를 의미하고, 따라서 정수 인수분해는 이들 클래스 둘 다를 벗어나는 것으로 널리 의심됩니다. 많은 사람들이 이에 대한 고전적인 다항식-시간 알고리듬을 찾으려고 시도해 왔지만 실패했고, 따라서 그것은 P 외부에 있는 것으로 널리 의심됩니다.

이에 반해, 결정 문제 "n은 합성수인가?" (또는 동등하게: "n은 소수인가?")는 n의 인수를 지정하는 문제보다 훨씬 쉬운 것처럼 보입니다. 합성수/소수 문제는 AKS 소수성 테스트(AKS primality test)를 갖는 다항식 시간 (n의 자릿수의 숫자 b)에서 해결될 수 있습니다. 게다가, 만약 우리가 아주 작은 오류의 가능성을 기꺼이 받아들일 의향이 있으면 실제로 소수성을 매우 빠르게 테스트할 수 있는 몇 가지 확률적 알고리듬(probabilistic algorithm)이 있습니다. 소수성 테스트(primality test)의 쉬움은 RSA 알고리듬의 치명적 부분인데, 왜냐하면 시작하기 위해 큰 소수를 찾아야 하기 때문입니다.

Factoring algorithms

Special-purpose

특수-목적 인수화 알고리듬의 실행 시간은 인수되려는 숫자의 속성이나 그것의 알려지지 않은 인수: 크기, 특수 형식, 등 중 하나에 따라 달라집니다. 실행 시간을 결정하는 매개변수는 알고리듬마다 다릅니다.

특수-목적 인수화 알고리듬의 중요한 하위클래스는 그것의 실행 시간이 가장 작은 소수 인수의 크기에 의존하는 Category 1 또는 First Category 알고리듬입니다. 알려지지 않은 형식의 정수가 주어지면, 이들 방법은 보통 작은 인수를 제거하기 위해 일반적인-목족 방법 전에 적용됩니다.[9] 예를 들어, 소박한 나눗셈 시도(trial division)는 카테고리 1 알고리듬입니다.

General-purpose

역시 Category 2, Second Category, 또는 크라이치키(Kraitchik) 가족 알고리듬이라고 불리는 일반-목적 인수화 알고리듬은 인수화되려는 정수의 크기에만 의존하는 실행 시간을 가집니다.[9] 이것은 RSA 숫자(RSA number)를 인수화하기 위해 사용되는 알고리듬의 유형입니다. 대부분의 일반-목적 인수화 알고리듬은 제곱의 적합성(congruence of squares) 방법을 기반으로 합니다.

Other notable algorithms

Heuristic running time

숫자 이론에서, 작은-o 및 L-표기법(L-notation)에서 경험적으로 예상된 실행 시간(running time)을 가지는 많은 정수 인수화 알고리듬이 있습니다:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle L_n\left[\tfrac12,1+o(1)\right]=e^{(1+o(1))\sqrt{(\log n)(\log \log n)}}} .

그들 알고리듬의 몇 가지 예제는 타원 곡선 방법(elliptic curve method)과 이차 체(quadratic sieve)입니다. 또 다른 그러한 알고리듬은 슈노르(Schnorr),[10] 세이센(Seysen),[11] 및 렌스트라(Lenstra)에[12] 의해 제안된 클래스 그룹 관계 방법(class group relations method)으로, 그들은 입증되지 않은 일반화된 리만 가설(Generalized Riemann Hypothesis, GRH)만을 가정하여 입증되었습니다.

Rigorous running time

슈노르–세이센–렌스트라 확률적 알고리듬은 렌스트라와 포머랜스(Pomerance)에[13] 의해 GRH 가정을 승수의 사용으로 대체함으로써 예상된 실행 시간 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle L_n\left[\tfrac12,1+o(1)\right]} 을 가지기 위해 엄격하게 입증되어 왔습니다. 그 알고리듬은 GΔ에 의해 표시되는 판별식(discriminant) Δ의 양의 이항 이차 형식(quadratic form)의 클래스 그룹(class group)을 사용합니다. GΔ는 정수 (a, b, c)의 삼중 집합으로, 이것에서 그들 정수는 상대적 소수입니다.

Schnorr–Seysen–Lenstra Algorithm

인수화되어야 할 정수 n이 주어지면, 여기서 n은 특정 정수보다 더 큰 홀수 양의 정수입니다. 이 인수화 알고리듬에서 판별식 Δ는 n의 배수, Δ = −dn로 선택되며, 여기서 d는 일부 양의 승수입니다. 그 알고리듬은 하나의 d에 대해 GΔ에서 충분한 매끄러운(smooth) 형식이 존재할 것으로 예상합니다. 렌스트라와 포머랜스는 d의 선택이 매끄러움 결과를 보장하기 위해 작은 집합으로 제한될 수 있음을 보여줍니다.

크로네커 기호(Kronecker symbol) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle \left(\tfrac{\Delta}{q}\right)=1} 를 갖는 모든 소수 q의 집합을 PΔ으로 나타냅니다. GΔ의 생성기(generators)의 집합과 PΔ에서 q를 갖는 GΔ의 소수 형식 fq를 건설함으로써, 생성기의 집합과 fq 사이의 관계의 수열이 생성됩니다. q의 크기는 일부 상수 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle c_0} 에 대해 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle c_0(\log|\Delta|)^2} 에 의해 경계질 수 있습니다.

사용되어야 할 관계는 GΔ의 중립 원소(neutral element)와 같은 거듭제곱의 곱 사이의 관계입니다. 이들 관계는 2를 나누는 차수의 GΔ의 원소인 GΔ 형식의 소위 모호한 형식을 구성하기 위해 사용될 것입니다. Δ의 해당하는 인수분해를 계산하고 gcd를 취함으로써, 이 모호한 형식은 n의 완전한 소수 인수분해를 제공합니다. 이 알고리듬은 다음과 같은 주요 단계를 가집니다:

n을 인수화되려는 숫자로 놓습니다.

  1. Δ를 Δ = −dn를 갖는 음의 정수로 놓습니다. 여기서 d는 승수이고 Δ는 일부 이차 형식의 음의 판별식입니다.
  2. 어떤 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle t\in{\mathbb N}} 에 대해, t 처음 소수 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle p_1=2,p_2=3,p_3=5, \dots ,p_t} 을 취합니다.
  3. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle f_q} 를 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle \left(\tfrac{\Delta}{q}\right)=1} 를 갖는 GΔ의 무작위 소수 형식으로 놓습니다.
  4. GΔ의 생성하는 집합 X를 찾습니다.
  5. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle \left(\prod_{x \in X_{}} x^{r(x)}\right).\left(\prod_{q \in P_\Delta} f^{t(q)}_{q}\right) = 1} 를 만족시키는 집합 X와 {fq : q ∈ PΔ} 사이의 관계의 수열을 모읍니다.
  6. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle \Delta = -4ac \text{ or } a(a - 4c) \text{ or } (b - 2a)(b + 2a)} 에서 Δ의 가장 큰 홀수 제수의 서로소 인수분해를 얻기 위해 2를 나누는 차수의 원소 f ∈ GΔ인 모호한 형식 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle (a, b, c)} 을 구성합니다.
  7. 만약 모호한 형식이 n의 인수분해를 제공하면 중지하고, 그렇지 않으면 n의 인수분해가 찾아질 때까지 또 다른 모호한 형식을 찾습니다. 불필요한 모호한 형식이 생성되는 것을 방지하기 위해, G(Δ)의 2-쉴로브(2-Sylow) 그룹 Sll2(Δ)을 구축합니다.

임의의 양의 정수를 인수화하는 알고리듬을 얻기 위해, 나눗셈 시도, 및 야코비 합 테스트(Jacobi sum test)와 같은 몇 가지 단계를 이 알고리듬에 추가할 필요가 있습니다.

Expected running time

명시된 알고리듬은 무작위 선택을 하기 때문에 확률적 알고리듬(probabilistic algorithm)입니다. 그것의 예상된 실행 시간은 많아야 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle L_n\left[\tfrac12,1+o(1)\right]} 입니다.[13]

See also

Notes

  1. ^ "[Cado-nfs-discuss] 795-bit factoring and discrete logarithms". Archived from the original on 2019-12-02.
  2. ^ Kleinjung; et al. (2010-02-18). "Factorization of a 768-bit RSA modulus" (PDF). International Association for Cryptologic Research. Retrieved 2010-08-09. {{cite journal}}: Cite journal requires |journal= (help)
  3. ^ Krantz, Steven G. (2011), The Proof is in the Pudding: The Changing Nature of Mathematical Proof, New York: Springer, p. 203, doi:10.1007/978-0-387-48744-1, ISBN 978-0-387-48908-7, MR 2789493
  4. ^ Arora, Sanjeev; Barak, Boaz (2009), Computational complexity, Cambridge: Cambridge University Press, p. 230, doi:10.1017/CBO9780511804090, ISBN 978-0-521-42426-4, MR 2500087
  5. ^ Goldreich, Oded; Wigderson, Avi (2008), "IV.20 Computational Complexity", in Gowers, Timothy; Barrow-Green, June; Leader, Imre (eds.), The Princeton Companion to Mathematics, Princeton, New Jersey: Princeton University Press, pp. 575–604, ISBN 978-0-691-11880-2, MR 2467561. See in particular p. 583.
  6. ^ Buhler, J. P.; Lenstra, H. W. Jr.; Pomerance, Carl (1993). Factoring integers with the number field sieve (Lecture Notes in Mathematics, vol 1554 ed.). Springer. pp. 50–94. doi:10.1007/BFb0091539. ISBN 978-3-540-57013-4. Retrieved 12 March 2021.
  7. ^ Vandersypen, Lieven M. K.; et al. (2001). "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance". Nature. 414 (6866): 883–887. arXiv:quant-ph/0112176. Bibcode:2001Natur.414..883V. doi:10.1038/414883a. PMID 11780055. S2CID 4400832.
  8. ^ Lance Fortnow (2002-09-13). "Computational Complexity Blog: Complexity Class of the Week: Factoring".
  9. ^ a b David Bressoud and Stan Wagon (2000). A Course in Computational Number Theory. Key College Publishing/Springer. pp. 168–69. ISBN 978-1-930190-10-8.
  10. ^ Schnorr, Claus P. (1982). "Refined analysis and improvements on some factoring algorithms". Journal of Algorithms. 3 (2): 101–127. doi:10.1016/0196-6774(82)90012-8. MR 0657269.
  11. ^ Seysen, Martin (1987). "A probabilistic factorization algorithm with quadratic forms of negative discriminant". Mathematics of Computation. 48 (178): 757–780. doi:10.1090/S0025-5718-1987-0878705-X. MR 0878705.
  12. ^ Lenstra, Arjen K (1988). "Fast and rigorous factorization under the generalized Riemann hypothesis". Indagationes Mathematicae. 50 (4): 443–454. doi:10.1016/S1385-7258(88)80022-2.
  13. ^ a b Lenstra, H. W.; Pomerance, Carl (July 1992). "A Rigorous Time Bound for Factoring Integers" (PDF). Journal of the American Mathematical Society. 5 (3): 483–516. doi:10.1090/S0894-0347-1992-1137100-0. MR 1137100.

References

External links

Retrieved from "https://dawoum.duckdns.org/w/index.php?title=Integer_factorization&oldid=81775"