정수 인수 분해

컴퓨터 과학의 미해결 문제:

정수 인수 분해는 고전적인 컴퓨터에서 다항 시간 내에 해결될 수 있습니까?

정수 인수분해()는 정수를 정수의 곱으로 분해하는 것을 의미합니다.요인이 소수로 더 제한되는 경우 이 공정을 소수 인수 분해라고 하며, 주어진 정수가 소수인지 여부(이 경우 단일 요인의 "곱"이 있음)에 대한 검정을 포함합니다.

숫자가 충분히 크면 효율적인 비양자 정수 인수 분해 알고리듬이 알려져 있지 않습니다.하지만, 그러한 알고리즘이 존재하지 않는다는 것은 증명되지 않았습니다.RSA 공개 키 암호화 및 RSA 디지털 ^[1]서명과 같은 암호화에 사용되는 알고리즘의 경우 이 문제의 예상 난이도가 중요합니다.타원 곡선, 대수적 숫자 이론, 그리고 양자 컴퓨팅을 포함하여 수학과 컴퓨터 과학의 많은 영역이 이 문제에 적용되었습니다.

2019년, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Tomé 및 Paul Zimmermann은 약 900년의 컴퓨팅 ^[2]성능을 활용하여 240자리(795비트) 숫자(RSA-240)를 제조했습니다.연구원들은 1024비트 RSA 계수가 약 500배의 ^[3]시간이 소요될 것으로 추정했습니다.

주어진 길이의 모든 숫자가 똑같이 인수 분해하기 어려운 것은 아닙니다.(현재 알려진 기술에 대해) 이러한 문제의 가장 어려운 예는 두 소수의 곱인 반 소수입니다.예를 들어 2,000비트 이상의 길이, 무작위로 선택된 크기, 거의 같은 크기일 때(예를 들어 페르마의 인수분해 방법에 의한 효율적인 인수분해를 피하기 위해 너무 가깝지는 않음), 가장 빠른 컴퓨터의 프라임 인수분해 알고리즘조차도 검색을 비실용적으로 만들기에 충분한 시간이 걸릴 수 있습니다.인수 분해되는 정수의 자릿수가 증가함에 따라 모든 컴퓨터에서 인수 분해를 수행하는 데 필요한 작업 수가 크게 증가합니다.

많은 암호화 프로토콜은 대규모 복합 정수를 고려하는 어려움이나 RSA 문제와 같은 관련 문제를 기반으로 합니다.임의 정수를 효율적으로 인수 분해하는 알고리즘은 RSA 기반 공개 키 암호화를 불안정하게 만듭니다.

원분해

산술의 기본 정리에 따르면, 모든 양의 정수는 고유한 소수 인수 분해를 가집니다.(일반적으로 1은 빈 제품입니다.)정수가 소수인지 여부를 검정하는 것은 예를 들어 AKS 소수성 검정을 통해 다항식 시간에 수행할 수 있습니다.그러나 복합적인 경우 다항 시간 검정은 요인을 얻는 방법에 대한 통찰력을 제공하지 않습니다.

정수 인수 분해에 대한 일반적인 알고리즘을 고려할 때, 이 알고리즘의 반복적인 적용으로 모든 정수를 구성하는 소수 인자로 인수 분해할 수 있습니다.특수 목적 인수 분해 알고리즘의 경우 상황이 더 복잡하며, 이 알고리즘의 이점은 분해 과정에서 생성된 요인으로도 실현되지 않거나 아예 실현되지 않을 수도 있습니다.예를 들어, p < q가 매우 큰 소수인 n = 171 x p x q인 경우, 시행 분할은 요인 3과 19를 빠르게 생성하지만 다음 요인을 찾기 위해 p 분할을 수행합니다.대조적인 예로, n이 소수 13729, 1372933 및 18848997161의 곱이라면, 여기서 13729 × 1372933 = 18848997157,페르마의 인수분해 방법은 $\left\lceil {\sqrt {n}}\right\rceil =18848997159$ $\left\lceil {\sqrt {n}}\right\rceil =18848997159$ ${\textstyle b={\sqrt {a^{2}-n}}={\sqrt {4}}=2}$ $\left\lceil {\sqrt {n}}\right\rceil =18848997159$ ({ $displaystyle \left\lceil$ \ $left\lceil =$ 18848997159)로 시작되며, ${\textstyle b={\sqrt {a^{2}-n}}={\sqrt {4}}=2}$ 는 $\left\lceil {n}}\right\rceil = 18848997159$ 즉시 b = ${\textstyle b={\sqrt {a^{2}-n}}={\sqrt {4}}=2}$ - n ${\textstyle b={\sqrt {a^{2}-n}}={\sqrt {4}}=2}$ ${\textstyle b={\sqrt {a^{2}-n}}={\sqrt {4}}=2}$ $=$ 2 $=$ 188{ $2}-n$ }, $따라서$ a - b = 18848997157188487188.이것들은 각각 합성과 소수로 쉽게 인식되지만, 페르마의 방법은 a에 대한 ${\textstyle \left\lceil {\sqrt {18848997157}}\,\right\rceil =137292}$ $18848997157$ ⌈ $=$ ${\textstyle \left\lceil {\sqrt {18848997157}}\,\right\rceil =137292}$ \ $textstyle$ \ $left\leceil = 137292의$ 시작 값이 1372933에 가깝지 않기 때문에 합성 수를 인수하는 데 훨씬 더 오래 걸릴 것입니다.

팩터링 알고리즘

특수 목적

특수 목적 팩터링 알고리즘의 실행 시간은 팩터링할 숫자의 속성 또는 크기, 특수 형식 등의 알려지지 않은 요인 중 하나에 따라 달라집니다.실행 시간을 결정하는 매개 변수는 알고리즘마다 다릅니다.

특수 목적 인수 분해 알고리즘의 중요한 하위 클래스는 범주 1 또는 첫 번째 범주 알고리즘이며, 실행 시간은 가장 작은 주 요인의 크기에 따라 달라집니다.알 수 없는 형식의 정수가 주어지면 이러한 방법은 일반적으로 작은 ^[10]요인을 제거하기 위해 범용 방법보다 먼저 적용됩니다.예를 들어, 순진한 시도 분할은 카테고리 1 알고리즘입니다.

재판부
휠 인수 분해
폴라드의 rho 알고리즘은 그룹 주기를 식별하는 두 가지 공통적인 맛을 가지고 있습니다: 하나는 플로이드에 의한 것이고 다른 하나는 브렌트에 의한 것입니다.
Pollard의 p - 1 알고리즘, Williams의 p + 1 알고리즘, Lenstra 타원 곡선 인수분해를 포함하는 대수적 그룹 인수분해 알고리즘
페르마 인수분해법
오일러 인수분해법
특수번호 필드 체

범용

범주 2, 두 번째 범주 또는 Kraitchik 계열 ^[10]알고리즘이라고도 하는 범용 인수 분해 알고리즘에는 인수 분해할 정수의 크기에만 의존하는 실행 시간이 있습니다.RSA 번호를 인수 분해하는 데 사용되는 알고리즘 유형입니다.대부분의 범용 인수분해 알고리즘은 제곱합 방법을 기반으로 합니다.

기타 주목할 만한 알고리즘

양자 컴퓨터를 위한 쇼어의 알고리즘

경험적 실행 시간

숫자 이론에서, 경험적으로 예상되는 실행 시간을 갖는 많은 정수 인수 분해 알고리즘이 있습니다.

L_{n}\left[{\tfrac {1}{2},1+o(1)\right]=e^{(1+o(1)){\sqrt {(\log n)(\log \log n)}}}}

little-o와 l-notation으로.이러한 알고리즘의 예로는 타원 곡선 방법과 2차 체가 있습니다.또 다른 그러한 알고리즘은 슈노르,^[11] 세이센,^[12]^[13] 렌스트라가 제안한 클래스 그룹 관계 방법으로, 증명되지 않은 일반화 리만 가설(GRH)만 가정하여 증명되었습니다.

엄격한 실행 시간

슈노르-세이센-렌스트라 확률 알고리듬은 GRH 가정을 승수를 사용하여 대체함으로써 예상 $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ Ln $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ + $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ o $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ ( $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ ) $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ ] {\ $displaystyle L_{n}\left[{\tfrac {1}{2}, 1+o(1)\right]}$ 이 $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ 렌스트라와 포메랑스에^[14] 의해 엄격하게 입증되었습니다.이 알고리즘은 G로 표시된_Δ 판별 Δ의 양의 이진 2차 형식 클래스 그룹을 사용합니다. G는_Δ 해당 정수가 상대적 소수인 정수(a, b, c)의 3중 집합입니다.

슈노르-세이센-렌스트라 알고리즘

인수가 될 정수 n이 주어지면, 여기서 n은 특정 상수보다 큰 홀수 양의 정수입니다.이 인수분해 알고리즘에서 판별자 Δ는 n의 배수인 Δ = -dn으로 선택되며, 여기서 d는 일부 양의 승수입니다.알고리즘은 G Lensstra와 Pomerance에 충분한_Δ 평활 형태가 존재할 것으로 예상합니다. d의 선택이 평활도 결과를 보장하기 위해 작은 세트로 제한될 수 있음을 보여줍니다.

P에 의해_Δ 크로네커 기호 $\left({\tfrac {\Delta }{q}}\right)=1$ q) $=$ $\left({\tfrac {\Delta }{q}}\right)=1$ {{ $displaystyle \left$ ({\ $tfrac {Delta }{q$ }\right)= $1$ 생성기 집합과_q 생성기 집합과 f 사이의 일련의 관계에서 q를_Δ 갖는 G의_Δ 소수_Δ 형태_q f를 생성함으로써.q의 크기는 일부 상수 c에₀ 대해 c(log Δ)²로 제한될₀ 수 있습니다.

사용될 관계는 G의 중성_Δ 요소와 동일한 힘의 곱 사이의 관계입니다.이러한 관계는 소위 모호한 형태의_Δ G를 구성하는 데 사용될 것이며, 이는 2를_Δ 나누는 순서의 G의 요소입니다.Δ의 해당 인수분해를 계산하고 gcd를 취함으로써 이 모호한 형태는 n의 완전한 소수 인수분해를 제공합니다.이 알고리즘에는 다음과 같은 주요 단계가 있습니다.

인수할 숫자를 n으로 합니다.

Δ가 Δ = -dn의 음의 정수라고 가정합니다. 여기서 d는 승수이고 Δ는 일부 2차 형식의 음의 판별식입니다.
t ∈ N에 대해 첫 번째 소수₁ p = 2, p₂ = 3, p₃ = 5, ..., p를_t 구합니다.
f가 ( ${\textstyle \left({\frac {\Delta }{q}}\right)=1}$ q ) $=$ ${\textstyle \left({\frac {\Delta }{q}}\right)=1}$ {{ $textstyle \left\frac {Delta$ } { $q}\right$ G의 임의의_Δ 소수 형태라고 하자_q.
G의 생성_Δ 집합 X를 찾습니다.
다음을 만족하는 집합_q X와 {f : q ${\textstyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1}$ ${\textstyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1}$ 사이의 관계 시퀀스를 수집합니다 ${\textstyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1}$ ( ${\textstyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1}$ ${\textstyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1}$ ${\textstyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1}$ $δ$ ${\textstyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1}$ t ( ${\textstyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1}$ ) ${\textstyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1}$ ${\textstyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1}$ ${\textstyle \left(\$ textstyle_ ${x\in$ X_ ${}}x^{r(x)}\r)}\$ right\ $left(\delta$ _ ${q\in$ P_ ${\Delta$ }} $f_{q}^{t(q)}\right)=1$
Δ = -4ac 또는 Δ = a(a - 4c) 또는 Δ Δ = (b - 2a)(b + 2a)인 Δ의 최대 홀수 인수분해를 얻기 위해 2를 나누는 원소 f Δ_Δ G인 모호한 형태(a, b, c)를 구성합니다.
모호한 형식이 n의 인수 분해를 제공하면 중지하고, 그렇지 않으면 n의 인수 분해가 발견될 때까지 다른 모호한 형식을 찾습니다.불필요한 모호한 형태가 생성되지 않도록 G(Δ)의 2-Sylow 그룹₂ Sll(Δ)을 구축합니다.

임의의 양의 정수를 인수분해하기 위한 알고리즘을 얻기 위해서는 이 알고리즘에 시행 분할 및 자코비 합 테스트와 같은 몇 가지 단계를 추가해야 합니다.

예상 실행 시간

언급된 알고리즘은 무작위 선택을 하기 때문에 확률론적 알고리즘입니다.예상 실행 시간은 $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ [ $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ + $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ ( $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ ] {\ $displaystyle L_{n}\left[{\tfrac {1}{2}, 1+o(1)\right$ ^[14]입니다.

참고 항목

오리페유 분해
인수분해로 난수를 생성하는 바흐의 알고리즘
양의 정수의 표준 표현
인수분해
곱셈 분할
${displaystyle$ p $}$ - 기본 $p$ 가치 평가
파티션(숫자 이론) – 양의 정수의 합으로 숫자를 쓰는 방법입니다.

메모들

^ Lenstra, Arjen K. (2011), "Integer Factoring", in van Tilborg, Henk C. A.; Jajodia, Sushil (eds.), Encyclopedia of Cryptography and Security, Boston, MA: Springer US, pp. 611–618, doi:10.1007/978-1-4419-5906-5_455, ISBN 978-1-4419-5905-8, retrieved 2022-06-22
^ "[Cado-nfs-discuss] 795-bit factoring and discrete logarithms". Archived from the original on 2019-12-02.
^ 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}}:저널 요구 사항 인용 journal=(도움말)
^ 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
^ 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
^ 특히 583페이지를 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참조하십시오.
^ 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. hdl:1887/2149. ISBN 978-3-540-57013-4. Retrieved 12 March 2021.
^ 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.
^ Lance Fortnow (2002-09-13). "Computational Complexity Blog: Complexity Class of the Week: Factoring".
^ ^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.
^ 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. Archived from the original on September 24, 2017.
^ 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.
^ Lenstra, Arjen K (1988). "Fast and rigorous factorization under the generalized Riemann hypothesis" (PDF). Indagationes Mathematicae. 50 (4): 443–454. doi:10.1016/S1385-7258(88)80022-2.
^ ^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.

레퍼런스

Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective. Springer. ISBN 0-387-94777-9. 5장: 지수 계수 알고리즘, 페이지 191–226.제6장: 하위 지수 계수 알고리즘, 페이지 227–284.섹션 7.4: 타원 곡선 방법, 페이지 301–313.
도널드 커누스.컴퓨터 프로그래밍의 기술, 제2권: 반숫자 알고리즘, 제3판애디슨 웨슬리, 1997년ISBN 0-201-89684-2.섹션 4.5.4: 소수에 대한 인수분해, 페이지 379–417.
Samuel S. Wagstaff Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3..
Warren, Henry S. Jr. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.

외부 링크

SIQS 및 NFS인 msieve는 알려진 가장 큰 공개 인수 분해를 완료하는 데 도움이 되었습니다.
리처드 P.Brent, "정수 인수분해 알고리즘의 최근 발전 및 전망", 컴퓨팅 및 조합론", 2000, 페이지 3–22. 다운로드.
Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES는 P에 있습니다." 수학연보 160(2): 781-793(2004).2005년 8월 버전 PDF
Eric W. Weisstein, "RSA-640 Factored" MathWorld 헤드라인 뉴스, 2005년 11월 8일
Dario Alpern의 정수 인수 분해 계산기 – 큰 정수 인수 분해를 위한 웹 앱

[1] Lenstra, Arjen K. (2011), "Integer Factoring", in van Tilborg, Henk C. A.; Jajodia, Sushil (eds.), Encyclopedia of Cryptography and Security, Boston, MA: Springer US, pp. 611–618, doi:10.1007/978-1-4419-5906-5_455, ISBN 978-1-4419-5905-8, retrieved 2022-06-22

[2] "[Cado-nfs-discuss] 795-bit factoring and discrete logarithms". Archived from the original on 2019-12-02.

[rsa768-3] 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}}:저널 요구 사항 인용 journal=(도움말)

[4] 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

[5] 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

[6] 특히 583페이지를 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참조하십시오.

[7] 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. hdl:1887/2149. ISBN 978-3-540-57013-4. Retrieved 12 March 2021.

[8] 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.

[9] Lance Fortnow (2002-09-13). "Computational Complexity Blog: Complexity Class of the Week: Factoring".

[Bressoud_and_Wagon-10] 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.

[1982-schnorr-11] 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. Archived from the original on September 24, 2017.

[1987-seysen-12] 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.

[1988-lenstra-13] Lenstra, Arjen K (1988). "Fast and rigorous factorization under the generalized Riemann hypothesis" (PDF). Indagationes Mathematicae. 50 (4): 443–454. doi:10.1016/S1385-7258(88)80022-2.

[lenstra-pomerance-14] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

v t 계산 경도 가정
수론	정수 인수 분해 피히딩 RSA 문제 강력한 RSA 이차잔류도 결정 합성 잔류물 높은 잔류성
군론	이산 로그 디피-헬먼 결정적 차이 -헬만 계산상의 어려움헬만
페어링	외부 차이 -헬만 하위 그룹 숨기기 의사결정 선형
격자	최단 벡터 문제(갭) 가장 가까운 벡터 문제(갭) 오류가 있는 학습 오류가 있는 링 학습 단정수해
비암호화	지수 시간 가설 고유 게임 추측 심어진 파벌 추측

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

v t 분할 기반 정수 집합
개요	정수 인수 분해 제수 유니터리 디바이어스 나눗셈 함수 주요인 산술의 기본 정리
요인화 양식	프라임 컴포지트 세미프라임 프로닉 스페니크 사각형 없음 강력한. 퍼펙트 파워 아킬레스 매끄러운 규칙적인. 러프 비일상적인.
제한된 나눗셈 합	완벽하네요. 거의 완벽함 준완전 완벽 곱셈 헤미퍼펙트 하이퍼퍼펙트 슈퍼퍼펙트 유니터리 퍼펙트 세미퍼펙트 실용적인. 에르되시-니콜라스
많은 디바인들과 함께.	풍부한 원시풍요 매우 풍부함 초풍부 엄청나게 풍부한. 고복합 우수한 고복합 재료 이상하다.
리쿼트 시퀀스 관련	언터처블 우호적(트리플) 사교적인 약혼녀
기저 의존적	등각 디지털 사치스러운 검소한 하샤드 다분수 스미스
기타집합	산술 부족한 친근하다. 고독한 숭고함 조화 지수 데카르트 리팩터블 슈퍼퍼펙트

Search