Heltalsfaktoriseringsposter
Heltalsfaktorisering är processen att bestämma vilka primtal som delar ett givet positivt heltal . Att göra detta snabbt har applikationer inom kryptografi . Svårigheten beror på både storleken och formen på talet och dess primfaktorer ; det är för närvarande mycket svårt att faktorisera stora semiprimtal (och faktiskt de flesta tal som inte har några små faktorer).
Siffror i en allmän form
Den första enorma distribuerade faktoriseringen var RSA-129 , ett 129-siffrigt utmaningsnummer som beskrivs i Scientific American-artikeln från 1977 som först gjorde RSA-kryptosystemet populärt. Den faktoriserades mellan september 1993 och april 1994, med hjälp av MPQS , med relationer som bidragit med cirka 600 personer via internet, och slutskedet av beräkningen utfördes på en MasPar superdator på Bell Labs.
Mellan januari och augusti 1999 faktoriserades RSA-155 , ett 155-siffrigt utmaningsnummer som utarbetats av RSA-företaget, med hjälp av GNFS med relationer som återigen bidragit med en stor grupp, och slutskedet av beräkningen utfördes på drygt nio dagar den Cray C916 superdator vid SARA Amsterdam Academic Computer Center.
I januari 2002, Franke et al. tillkännagav faktoriseringen av en 158-siffrig kofaktor på 2 953 +1, med ett par månader på cirka 25 datorer vid universitetet i Bonn , med de sista stegen med ett kluster av sex Pentium-III-datorer.
I april 2003 räknade samma team den 160-siffriga RSA-160 med hjälp av ett hundratal processorer vid BSI , och de sista stegen av beräkningen gjordes med 25 processorer i en SGI Origin -superdator.
576-bitars (174-siffriga) RSA-576 faktoriserades av Franke, Kleinjung och medlemmar av NFSNET -samarbetet i december 2003, med hjälp av resurser vid BSI och universitetet i Bonn; kort därefter meddelade Aoki, Kida, Shimoyama, Sonoda och Ueda att de hade räknat med en 164-siffrig kofaktor på 2 1826 +1.
En 176-siffrig kofaktor på 11 281 +1 beräknades av Aoki, Kida, Shimoyama och Ueda mellan februari och maj 2005 med hjälp av maskiner vid NTT och Rikkyo University i Japan.
Det 663-bitars (200-siffriga) RSA-200- utmaningsnumret faktoriserades av Franke, Kleinjung et al. mellan december 2003 och maj 2005, med ett kluster av 80 Opteron-processorer vid BSI i Tyskland; tillkännagivandet gjordes den 9 maj 2005. De tog senare (november 2005) hänsyn till det något mindre RSA-640- utmaningsnumret.
Den 12 december 2009 faktoriserade ett team med forskare från CWI , EPFL , INRIA och NTT förutom författarna till det tidigare rekordet RSA-768 , en 232-siffrig semiprime. De använde motsvarande nästan 2000 års datoranvändning på en enkelkärnig 2,2 GHz AMD Opteron .
faktoriserades 795-bitars (240-siffriga) RSA-240 av Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé och Paul Zimmermann.
slutfördes faktoriseringen av 829-bitars (250-siffriga) RSA-250 .
Siffror av en speciell form
12 151 − 1, på 542 bitar (163 siffror), faktoriserades mellan april och juli 1993 av ett team vid CWI och Oregon State University .
2 773 + 1, av 774 bitar (233 siffror), faktoriserades mellan april och november 2000 av 'The Cabal', med matrissteget gjort under 250 timmar på Cray som också användes för RSA-155.
2 809 − 1, av 809 bitar (244 siffror), fick sin faktorisering tillkännagiven i början av januari 2003. Siktning gjordes vid CWI, vid Scientific Computing Institute och Pure Mathematics Department vid Bonns universitet, och med hjälp av privata resurser av J. Franke, T. Kleinjung och familjen F. Bahr. Det linjära algebrasteget gjordes av P. Montgomery vid SARA i Amsterdam.
6 353 − 1, av 911 bitar (275 siffror), faktoriserades av Aoki, Kida, Shimoyama och Ueda mellan september 2005 och januari 2006 med SNFS .
2 1039 − 1, av 1039 bitar (313 siffror) (även om en faktor på 23 bitar redan var känd) faktoriserades mellan september 2006 och maj 2007 av en grupp inklusive K. Aoki, J. Franke, T. Kleinjung, AK Lenstra och DA Osvik, med datorer vid NTT , EPFL och universitetet i Bonn .
2 1061 − 1, av 1061 bitar (320 siffror) faktoriserades mellan början av 2011 och 4 augusti 2012 av en grupp ledd av Greg Childers på CSU Fullerton, som använde nfs@home BOINC-projektet för cirka 300 CPU-år av siktning ; den linjära algebra kördes vid Trestles-klustret vid SDSC och Lonestar-klustret vid TACC och behövde ytterligare 35 CPU-år.
Alla opåverkade delar av siffrorna 2 n − 1 med n mellan 1000 och 1200 faktoriserades av en flertalssiktsmetod där mycket av siktningssteget kunde göras samtidigt för flera tal, av en grupp inklusive T. Kleinjung, J. Bos och AK Lenstra , med start 2010. För att vara exakt slutfördes n =1081 (326 siffror) den 11 mars 2013; n =1111 (335 siffror) den 13 juni 2013; n =1129 (340 siffror) den 20 september 2013; n =1153 (348 siffror) den 28 oktober 2013; n =1159 (349 siffror) den 9 februari 2014; n =1177 (355 siffror) den 29 maj 2014, n =1193 (360 siffror) den 22 augusti 2014 och n =1199 (361 siffror) den 11 december 2014; det första detaljerade tillkännagivandet gjordes i slutet av augusti 2014. Den totala ansträngningen för projektet är i storleksordningen 7500 CPU-år på 2,2 GHz-opteroner, med ungefär 5700 år till siktning och 1800 år på linjär algebra.
Jämförelse med individers insatser
Från och med slutet av 2007, tack vare den ständiga nedgången i minnespriserna, lättillgängligheten av flerkärniga 64-bitarsdatorer och tillgången till den effektiva siktningskoden (utvecklad av Thorsten Kleinjung från Bonn-gruppen) via ggnfs och av robust programvara med öppen källkod som msieve för efterbehandlingsstadierna, nummer i specialformat på upp till 750 bitar (226 siffror) och allmänna tal på upp till cirka 520 bitar (157 siffror) kan räknas in på några månader på en få datorer av en enda person utan någon speciell matematisk erfarenhet. Dessa gränser ökar till cirka 950 bitar (286 siffror) och 600 bitar (181 siffror) om det var möjligt att säkra samarbetet mellan några dussin datorer för siktning; för närvarande är mängden minne och CPU-kraften för en enda maskin för slutsteget lika hinder för framsteg.
År 2009 faktoriserade Benjamin Moody en 512-bitars (155-siffrig) RSA-nyckel som användes för att signera grafräknaren TI-83 med hjälp av programvara som finns på internet; detta ledde så småningom till att Texas Instruments undertecknade en nyckelkontrovers .
faktoriserades 696-bitars (210-siffriga) RSA-210 av Ryan Propper med hjälp av institutionella resurser; mellan mars 2013 och oktober 2014 slutfördes ett annat 210-siffrigt nummer (den 117:e termen i primtalssekvensen som börjar med 49) av en användare känd som WraithX, och använde 7 600 USD i behandlingstid på Amazon EC2-maskiner för siktningen, och fyra månader på en dubbel Xeon E5-2687W v1 för linjär algebra.
Rekord för insatser av kvantdatorer
Det största antalet som tillförlitligt beräknas av Shors algoritm är 21, vilket räknades in 2012. 15 hade tidigare räknats in av flera labb.
rapporterades faktoriseringen av av en rumstemperatur (300K) NMR adiabatisk kvantdator av en grupp ledd av Xinhua Peng. I november 2014 upptäcktes det att experimentet 2012 faktiskt också hade räknat med mycket större siffror utan att veta om det. [ förtydligande behövs ] I april 2016 faktoriserades 18-bitars nummer 200 099 med hjälp av kvantglödgning på en D-Wave 2X kvantprocessor. Kort därefter faktoriserades 291 311 med användning av NMR vid högre temperatur än rumstemperatur. I slutet av 2019 Zapata computing att ha faktoriserat 1 099 551 473 989 och släppte 2021 ett papper som beskrev denna beräkning.
I december 2022 slutfördes 48-bitars faktoriseringen av 10-chips supern processor med hjälp av 10-chips-processor i Kina. Teamet räknade också med 11-bitars heltal 1961 och 26-bitars heltal 48567227 med 3 respektive 5 supraledande qubits. Tillvägagångssättet beskrevs dock av teamet som en "klassisk-kvanthybrid", som använder den ungefärliga kvantoptimeringsalgoritmen för att optimera den tidskrävande sr-pargenereringen som används i Schnorrs factoringalgoritm, och en klassisk dator för att lösa de resulterande linjära ekvationerna .
Som sådana har påståenden om factoring med kvantdatorer dock kritiserats för att vara starkt beroende av klassisk beräkning för att minska antalet qubits som krävs. Till exempel förlitade sig faktoriseringen på 1 099 551 473 989 på klassisk förbearbetning för att reducera problemet till en kvantkrets med tre kvantbitar. Dessutom kan de tre siffrorna som faktoriseras i denna artikel (200 099, 291 311 och 1 099 551 473 989) enkelt faktoriseras med Fermats faktoriseringsmetod , som endast kräver 3, 1 respektive 1 iterationer av slingan.