정수 인자화 레코드

정수 인자화는 어떤 소수들이 주어진 양의 정수를 나누는지 결정하는 과정이다.이것을 빨리 하면 암호학에서 응용이 가능하다.난이도는 숫자의 크기와 형태, 그리고 그것의 주요 요인 모두에 달려있다; 현재 큰 반시기를 고려하는 것은 매우 어렵다.

일반양식의 번호

최초의 대규모 분산 인자는 RSA-129로, RSA 암호 시스템을 최초로 대중화한 1977년 Scientific American 기사에 기술된 도전 번호였다.1993년 9월부터 1994년 4월 사이에 MPQS를 사용하여 인터넷을 통해 약 600명이 기여하는 관계와 계산의 최종 단계는 Bell Labs의 MasPar 슈퍼 컴퓨터에서 수행되었다.

1999년 1월부터 8월 사이에, RSA 회사가 작성한 도전 번호인 RSA-155는 GNFS를 이용하여 큰 그룹에 의해 다시 기여되었으며, 최종 계산 단계는 SARA 암스테르담 학술 컴퓨터 센터의 Cray C916 슈퍼 컴퓨터에서 불과 9일 만에 수행되었다.

2002년 1월, Franke 외 연구진은 본 대학의 약 25대의 PC에 두어 달 동안 2⁹⁵³+1의 158자리의 공동 인자화를 발표했으며, 최종 단계는 6개의 펜티엄-III PC로 구성된 클러스터를 사용하여 수행되었다.

2003년 4월, 동일한 팀이 BSI에서 약 100개의 CPU를 사용하여 RSA-160을 인수했으며, 계산의 최종 단계는 SGI 오리진 슈퍼 컴퓨터의 25개의 프로세서를 사용하여 수행되었다.

576비트 RSA-576은 2003년 12월 Franke, Kleinjung, NFSNET 협력회원들이 BSI와 본대학의 자원을 이용해 인수했으며, 곧이어 아오키, 키다, 시모야마, 소노다, 우에다 등이 164자리의 공동 인자 2¹⁸²⁶+1을 인수했다고 발표했다.

아오키, 키다, 시모야마, 우에다에 의해 2005년 2월부터 5월 사이에 일본의 NTT동서와 릿쿄대학의 기계를 이용하여²⁸¹ 11+1의 176자리의 공분자가 인수되었다.^[1]

663비트 RSA-200 챌린지 번호는 2003년 12월부터 2005년 5월까지 Franke, Kleinjung 등이 독일 BSI에서 80개의 Opteron 프로세서로 구성된 클러스터를 사용하여 조사했으며, 2005년 5월 9일에 발표되었다.^[2]이후(2005년 11월) 다소 작은 RSA-640 챌린지 번호를 고려했다.

2009년 12월 12일, 종전 기록의 작성자 외에 CWI, EPNL, INRIA, NTT의 연구자를 포함한 팀은 232자리수 세미프라임으로 RSA-768을 인수했다.^[3]그들은 단일 코어 2.2GHz AMD Opteron에서 거의 2000년의 컴퓨팅에 상당하는 것을 사용했다.

2019년 11월 795비트 RSA-240은 Fabrice Boudot, Pierrick Gaudry, Aurore Guilvic, Nadia Heninger, Emilan Thomé, Paul Zimmermann이 인수했다.^[4][5]

2020년 2월에는 829비트 RSA-250의 인수화가 완료되었다.^[6]

특수 양식의 번호

542비트(163자리) 중 12¹⁵¹ - 1은 CWI와 오리건 주립대학의 팀에 의해 1993년 4월과 7월 사이에 인수되었다.^[7]

774비트(233자리) 중 2⁷⁷³ + 1은 2000년 4월부터 11월 사이에 'The Cabal'에 의해 인수되었으며, 매트릭스 스텝은 RSA-155에도 사용되는 Cray에서 250시간 이상 수행되었다.^[8]

809비트(244자리) 중 2⁸⁰⁹ - 1은 2003년 1월 초에 계수화가 발표되었다.지빙은 CWI, 본대학 과학컴퓨팅연구소, 순수수학부 등에서 이루어졌으며, J. 프랑케, T.클라인중, F.가족의 사재를 이용했다.바흐. 선형 대수 단계는 P에 의해 이루어졌다.암스테르담에 있는 사라의 몽고메리.^[9]

911비트(275자리) 중 6³⁵³ - 1은 2005년 9월부터 2006년 1월까지 SNFS를 이용하여 아오키, 키다, 시모야마, 우에다에 의해 인수되었다.^[10]

1039비트(313자리) 중 2¹⁰³⁹ - 1(이미 23비트의 인수는 알고 있었지만)은 K를 포함한 그룹에 의해 2006년 9월부터 2007년 5월 사이에 인수되었다.아오키, J. 프랑케, T. 클라인정, A. K. 렌스트라, D.A. Osvik, NTT, EPFL, 본 대학의 컴퓨터를 사용한다.^[11][12]

2¹⁰⁶¹ − 1, of 1061 bits (320 digits) was factored between early 2011 and 4 August 2012 by a group headed by Greg Childers at CSU Fullerton, using the nfs@home BOINC project for about 300 CPU-years of sieving; the linear algebra was run at the Trestles cluster at SDSC and the Lonestar cluster at TACC and needed additional 35 CPU-years.^[13]

1000과 1200 사이의 n을 가진 숫자ⁿ 2 - 1의 모든 비공식 부분은 2010년부터 T. 클라인정, J. Bos, A. K. Lenstra를 포함한 그룹이 다수의 숫자에 대해 체이빙 단계의 많은 부분을 동시에 수행할 수 있는 복수 숫자 산출 접근법에 의해 고려되었다.^[14]To be precise, n=1081 was completed on 11 March 2013; n=1111 on 13 June 2013; n=1129 on 20 September 2013; n=1153 on 28 October 2013; n=1159 on 9 February 2014; 1177 on May 29, 2014, n=1193 on 22 August 2014, and n=1199 on December 11, 2014; the first detailed announcement was made in late August 2014.이 프로젝트를 위한 총 노력은 2.2GHz Opterons에 7500 CPU-년이며, 약 5700년이 소요되었고 1800년이 선형 대수학에 소요되었다.

개인의 노력과 비교

2007년 말에 메모리 가격의 지속적으로 하락하고 멀티 코어 64비트 컴퓨터의 준비의 가용성, 효율적인 여과기 코드(토르스텐 Kleinjung은 본 그룹이 개발)의 ggnfs[15]과 골인 단계,의 special-form 번호를 msieve[16] 같은 강력한 오픈 소스 소프트웨어를 통해 가용성 덕분에.750명에 이르고특별한 수학 경험 없이 한 사람이 몇 대의 PC에서 몇 달 안에 520비트까지의 비트와 일반 형식 번호를 인수할 수 있다.^[17]이러한 한계는 체이빙을 위해 수십 대의 PC의 협업을 확보할 수 있다면 약 950대와^[18] 600대로^[19] 증가하는데, 현재 단일 시스템의 메모리 양과 CPU 파워는 동일한 진행 장벽이다.

2009년, 벤자민 무디스는 인터넷에서 발견된 소프트웨어를 사용하여 TI-83 그래핑 계산기에 서명하는 데 사용되는 512비트 RSA 키를 인수했는데, 이는 결국 텍사스 인스트루먼트사가 핵심 논란에 서명하게 되었다.

9월 2013년에는 696-bit RSA-210 라이언 Propper[20]제도적 리소스를 사용하여 3월 2013년과 10월 2014년까지, 다른210-digit 수(는 '가정 주요 시퀀스에 있는 117용어'49부터 시작하여)사용자 WraithX,[21]AmazonEC2machines[22]에 siev달러를 7600 가치를 처리 시간을 사용하는 것과 알려진에 의해 완성된 수치를 생각했다.왕, 그리고 four 선형대수의 경우 이중 Xeon E5-2687W v1에 대한 월.

양자 컴퓨터의 노력에 대한 기록

Shor의 알고리즘에 의해 신뢰성 있게 인수된 가장 큰 숫자는 2012년에 인수된 21이다.^[23] 15는 이전에 여러 연구소에서 인수된 적이 있다.

2012년 4월, 실온(300K) NMR 아다바틱 양자컴퓨터에 의한$$ ${\displaystyle 143}$= ${\displaystyle 13}$ ${\displaystyle \times }$ ${\displaystyle 11}$ $[\displaystyle 143=13\times 11}$의 인수인자를 신화 펭이 이끄는 집단에 의해 보고하였다.^[24]2014년 11월, 2012년 실험은 실제로 그것을 알지 못한 채 훨씬 더 많은 숫자들을 고려했다는 것이 밝혀졌다.^[25][26]2016년 4월, 18비트 번호 200 099는 D-Wave 2X 양자 프로세서에서 양자 아닐링을 사용하여 인수되었다.^[27]얼마 후, 291 311은 상온보다 높은 NMR을 사용하여 인수되었다.^[28]2019년 말, 업계 협력 결과 1,099,551,473,989는 1,048,601을 곱한 1048,589와 같다.^[29]

참고 항목

• 알려진 최대 소수

참조