1 039-bitové číslo rozložené na súčin prvočísel

DSL.sk, 22.5.2007

Kryptografom z Bonnskej univerzity, švajčiarskeho EPFL a japonského NTT sa podarilo faktorizovať, rozložiť na súčin prvočísel, číslo dlhé 1 039 bitov, respektíve 307 desiatkových číslic.

Výpočet bol realizovaný na výpočtových klasteroch týchto troch inštitúcií 11 mesiacov, trval 100 rokov výpočtového času vyjadreného v CPU-hodinách.

Efektívne subexponenciálne rozloženie veľkého čísla na prvočísla by znamenalo okamžité prelomenie napríklad asymetrického algoritmu RSA, ktorý sa spolieha práve na to, že faktorizáciu nie je možné uskutočniť v lepšom ako exponenciálnom čase.

RSA sa v súčasnosti už často nahrádza novšími algoritmami, respektíve sa používa s minimálne 2 048-bitovými kľúčmi. Veľmi veľa aplikácií je ale stále chránených ešte 1 024-bitovým RSA.

Novšie asymetrické algoritmy sú založené na probléme diskrétneho logaritmu alebo elliptic curve cryptography, ktoré efektívna faktorizácia priamo neohrozuje.

Kryptografici ale zatiaľ nevyvinuli efektívny algoritmus na faktorizáciu ľubovoľného čísla o veľkosti rádovo 1 000 bitov, faktorizované číslo malo špeciálny tvar 2 ^ 1039 - 1 a použitý bol naňho algoritmus vyvinutý Arjenom Lenstrom a ďalšími matematikmi na konci 80-tych rokoch.

Lenstra, ktorý bol súčasťou tímu faktorizujúci toto číslo, ale upozornil, že u čísel polovičnej veľkosti (155 desiatkových číslic) sa podarilo nakoniec zovšeobecniť pôvodný algoritmus aj na ľubovoľné čísla, hoci tento proces trval deväť rokov.

Najväčšie všeobecné číslo rozložené na súčin prvočísel má 200 desiatkových číslic, rozložené bolo v roku 2005 po 18 mesiacoch výpočtov a 50 rokoch výpočtového času.


Najnovšie články:



Diskusia:

mato Od: mato | Pridané: 22.5.2007 12:30 heh .. takze na mojom kompe by to trvalo 100 rokov ? fuh Odpovedať Hodnotiť:

Backslash Od: Backslash | Pridané: 22.5.2007 12:32 No, ak by si mal len jeden procesor identický s tým, ktorý bol použitý pri výpočtoch, tak áno. Odpovedať Hodnotiť:

Otazka Od: Otazka | Pridané: 22.5.2007 19:00 Viem ze to je dolezite ale co vlastne vypocitali ako by som to spravil s 8bit cislom? Odpovedať Hodnotiť:

PITON Od: PITON | Pridané: 23.5.2007 14:41 8 bitov to je max.=2^8=256 cize 0-255 a cislo 255 rozlozene na sucin prvocisel je 255=3*5*17 :) Odpovedať Hodnotiť:

tonic747 Od: tonic747 | Pridané: 22.5.2007 12:59 To znamena zeby ti to trvalo ovela dlhsie :))) Odpovedať Hodnotiť:

lordiceman Od: lordiceman | Pridané: 22.5.2007 13:06 to je fakt vedecka praca nechat x kompov riesit nejaky zbytocny vypocet 11 mesiacov... ano, pravdaze ten algoritmus je vedeckou pracou, ale netusim na co treba potom nechat 11 mesiacov faktorizovat jedno jedine cislo... trapne Odpovedať Hodnotiť:

krigel Od: krigel | Pridané: 22.5.2007 13:12 asi chceli dokazat ze to naozaj funguje Odpovedať Hodnotiť:

Miroslav Bakoš Od: Miroslav Bakoš | Pridané: 22.5.2007 13:51 a ako zistili ze to naozaj funguje? :) Odpovedať Hodnotiť:

Propediotika Od: Propediotika | Pridané: 22.5.2007 17:07 No predsa zistili sucin prvocisiel daneho cisla :) Odpovedať Hodnotiť:

Miroslav Bakoš Od: Miroslav Bakoš | Pridané: 23.5.2007 6:10 a ako zistia ci je vypocet spravny? :-) prepocital to niekto rucne? vies aka je chybovost vypoctov procesora za 11 mesiacov? :-) Odpovedať Hodnotiť:

Adam Od: Adam | Pridané: 23.5.2007 22:28 procesoru skoro nulová, větší chyb budou v sowtwaru. Odpovedať Hodnotiť:

zippy Od: zippy | Pridané: 24.5.2007 15:40 neviem, zeby vynasobili tie 2 prvocisla medzi sebou a ked dostanu povodne cislo prehlasia to za riesenie? sak rozmylam, nie? Odpovedať Hodnotiť:

mirres Od: mirres | Pridané: 22.5.2007 16:34 hmm no neveim ci je trapne to alebo ty, ale skor ty, lebo na tomto je postavene takmer vsetko dnesne sifrovanie. a neviem ci by ti bolo prijemne, keby to sifrovanie prebiehalo pomocou nejakeho "trapneho" 10 bitoveho cisla a potom niekto by ti trapne rozlustil pristupove udaje ku kreditke a potom tak "trapne" ju vybral. nabuduce si aspon zisti o co ide, ked sa k necomu vyjadris! Odpovedať Hodnotiť:

palo Od: palo | Pridané: 22.5.2007 18:19 lordiceman: keby si vedel nieco o kryptografii, mozno by si vynechal v tvojom prispevku slovne spojenia ako napr.: "nejaky zbytocny vypocet" alebo "netusim na co treba" pripadne "trapne". na asymetrickej kryptografii je zalozena bezpecnost nespocetne vela veci a som si isty, ze niektore z nich pouzivas aj ty a ani o tom zjavne nevies. prikladam zaujimavy link: http://www.rsa.com/rsalabs/node.asp?id=2093 aj napriek tomu ze rsa challenge uz nie je aktivna, nachadza sa tam mnozstvo zaujimavych informacii. kryptografii zdar! Odpovedať Hodnotiť:

opec Od: opec | Pridané: 22.5.2007 13:44 mimo mojho chapania ---> staci len ze to ide :) Odpovedať Hodnotiť:

opec Od: opec | Pridané: 22.5.2007 13:55 inac este by ma zaujimalo kolko by to trvalo huckovi norrisovi. ale ne vazne kolko by to robila skupinka 100 vedcov? mozog moze byt asi tak 20GHz ale iba jedno jadro a nepodporuje multitasking <--- muzi a zeny su 8GHz ale 2x a podporuju multitasking. vlastne zajimave : mame 2hemisfery a nepodporujeme multitasking :) PS: kolko Mpix je oko? Odpovedať Hodnotiť:

mikosuo Od: mikosuo | Pridané: 22.5.2007 14:07 no zaujimave co si napisal sice som akosi nepochopil polovicu :-) aj ja chcem vediet kolko Mpx ma oko tipujem aspon 100 Odpovedať Hodnotiť:

Nerte Od: Nerte | Pridané: 22.5.2007 14:13 100??! Sa spamataj, co si orol?? Urcite do 10 - tak 7 by som tipol. Odpovedať Hodnotiť:

mikosuo Od: mikosuo | Pridané: 22.5.2007 14:16 a mi povedz ze 10 mpx fotak urobi lepsi obraz ako tvoje oko Odpovedať Hodnotiť:

Nassir Od: Nassir | Pridané: 22.5.2007 14:48 Takmer urcite ano. Ostro vidime len na zltej skvrne v strede a cele periferne videnie je len rozmajznuty blivajs - takze ja osobne to odhadujem tak na 100 Kpixel max. Neoverene "zkazky" totiz hovoria, ze vyuzivana prenosova kapacita ocneho nervu je len niekolko kB, kedze pohyb a zmena podnetov sa prenasa prioritne a ostatne udaje si mozog dopocitava. Na druhej strane - ci uz interpolovane alebo nie, tak oko obsahuje 130 milionov tyciniek a 7 milionov capikov, takze mame farebny 7Mpixel alebo 130 Mpixel ciernobiely. Odpovedať Hodnotiť:

opec Od: opec | Pridané: 22.5.2007 15:38 chlapeeec, ze jaka profesionalita, som nevedel kolko je tyciniek a capikov :) Odpovedať Hodnotiť:

y0g Od: y0g | Pridané: 22.5.2007 16:25 tak ja budem radsej pozerat CB ale vo vyssej kvalite :)) Odpovedať Hodnotiť:

Nerte Od: Nerte | Pridané: 22.5.2007 14:11 Vies ze kazda hemisfera robi nieco ine, ze? Prava su emocie a kreativita a lava je logika vypocty atd... Odpovedať Hodnotiť:

opec Od: opec | Pridané: 22.5.2007 15:39 ano ale nedokaze robit 2veci naraz, a preto nemozeme telefonovat ked riadime Odpovedať Hodnotiť:

Uhlik Od: Uhlik | Pridané: 22.5.2007 16:01 ale dokazeme napriklad citat diskusiu a trhat si chlpy z nosa ;o) ... Odpovedať Hodnotiť:

Meno musí mať dĺžku aspoň 3znaky Od: Meno musí mať dĺžku aspoň 3znaky | Pridané: 22.5.2007 16:41 alebo vytlacat jebaky Odpovedať Hodnotiť:

MaoBK Od: MaoBK | Pridané: 22.5.2007 16:59 Vlastne mi teraz sucasne bije srdce, dycham, potim bo je teplo, pisem, citam, a sucasne mi pracuje viac ako sto svalov, od mimiky az po prsty v nose, ak toto nieje multy tak co??? Mimochodom task`s s najvacsou prioritou robim auto ani na ne nemyslim. Len na kontrolu preklepou mi ostalo malo dostupneho vypoctoveho priestoru :). Odpovedať Hodnotiť:

opec Od: opec | Pridané: 22.5.2007 19:52 veci na ktore sa musime sustredit. skus si to. Odpovedať Hodnotiť:

Tinki binky Od: Tinki binky | Pridané: 22.5.2007 20:26 No napriklad ja ked si honim dokazem si obzerat porono casopis, a v intervaloch prevraciat strany :oD Odpovedať Hodnotiť:

opec Od: opec | Pridané: 22.5.2007 22:09 nebojsa, z toho vyrasties (mozno) Odpovedať Hodnotiť:

a3a3a3 Od: a3a3a3 | Pridané: 22.5.2007 14:20 Apropo ludske oko nie je velmi vyvinute.... Len pre zaujimavost specifikacia ludskeho oka na wikipedii Externý blesk: nie Ďiaľkové ovládanie: nie Závit na statív: nie Podpora priameho tlačenia: lol Konektory: nie Režimy vstavaného blesku: off Redukcia červených očí: nie Histogram: nie Zoom pri prozeraní: nie nj, oci su uz proste out Odpovedať Hodnotiť:

Lubbo Od: Lubbo | Pridané: 22.5.2007 19:53 lool Odpovedať Hodnotiť:

Adam Od: Adam | Pridané: 23.5.2007 22:30 Nesouhlasím, redukcu červených očí máme :-) Odpovedať Hodnotiť:

someone Od: someone | Pridané: 22.5.2007 14:31 chuck norris by povedal vysledok a to cislo by sa zo strachu pred nim sformovalo do takeho tvaru aby to sedelo :-) Odpovedať Hodnotiť:

Uhlik Od: Uhlik | Pridané: 22.5.2007 16:05 chuck norris faktorizoval nekonecno ... dva krat ... Odpovedať Hodnotiť:

tipsy Od: tipsy | Pridané: 22.5.2007 20:28 nie on napocital do nekonecna............ .......... dva krat Odpovedať Hodnotiť:

onesome Od: onesome | Pridané: 22.5.2007 14:38 Chuck Norris by urcite isiel radsej sem: http://s4.bitefight.cz/c.php?uid=18041 ako pocitat nejake primitivne cislo Odpovedať Hodnotiť:

Adrian312 Od: Adrian312 | Pridané: 22.5.2007 15:23 OMG sa prosim ta uvedom. kolko ludi ti na to uz naskocilo??? to radssej daju tie porno stranky od spam botov co su tu. si ako maly chlapec. A Chuck Norris by ti za tot zlomil tvar tak bud rad ze nie som Chuck Odpovedať Hodnotiť:

Od: | Pridané: 22.5.2007 15:51 Jeden dobrý dôvod prečo je tá hra dobrá? Lebo keď na niekoho zaútočíš musíš čakať ako dáky trtko 15 minút? lebo keď ideš na lov, tak počas lovu nemôžeš nič robiť (10-120 minút), medzi 12x10 a 120 minútami lovu je v koristi priepastný rozdiel- na čase nezáleží, lov ako lov (za deň max 120 minút na to určených), a takto sa to celé premrhá, niektoré itemy sa nedajú získať bez takého otravného spamovania a platenia.. fakt super.. a zábava.. Odpovedať Hodnotiť:

mikosuo Od: mikosuo | Pridané: 22.5.2007 15:54 no pozeram ze to hras ked to tak ovladas Odpovedať Hodnotiť:

gggg Od: gggg | Pridané: 22.5.2007 17:05 o kerej pici je rec ? Odpovedať Hodnotiť:

mikosuo Od: mikosuo | Pridané: 22.5.2007 17:33 no nahodou sme sa bavili o tvojej pici no prepac :-) Odpovedať Hodnotiť:

Od: | Pridané: 23.5.2007 9:22 tak na to aby som niečo hodnotil najprv zistím čo to je, nie? alebo budem hodnotiť na základe toho že susedovie jožko povedal, že to stojí za ...? Odpovedať Hodnotiť:

Lala Od: Lala | Pridané: 22.5.2007 20:29 naletel ti vobec niekto na o Odpovedať Hodnotiť:

fú.... Od: fú.... | Pridané: 22.5.2007 16:25 šak jasné...nie? Odpovedať Hodnotiť:

feinomore Od: feinomore | Pridané: 22.5.2007 17:03 Satko by to zvladol s Riecanovou za hodinu. Odpovedať Hodnotiť:

MurdocNZ Od: MurdocNZ | Pridané: 23.5.2007 10:33 A Kollar to vypocital uz v deviatej ludovej na domacu ulohu :) Odpovedať Hodnotiť:

fejkar Od: fejkar | Pridané: 22.5.2007 17:19 A Volauf za 30 min. Odpovedať Hodnotiť:

volauf Od: volauf | Pridané: 22.5.2007 18:07 a este by som k tomu stihol spomenut tri kvazi ftipne prihody z moje staze v US and A :P Odpovedať Hodnotiť:

panc0 Od: panc0 | Pridané: 22.5.2007 17:34 elliptic curve cryptography , to sa uz nedalo prelozit ako kyptografia na baze eliptickych kriviek? Odpovedať Hodnotiť:

Albert E. Od: Albert E. | Pridané: 22.5.2007 18:14 No uz zas sa debata stocila do debilneho neznama :) Odpovedať Hodnotiť:

Bozzz Od: Bozzz | Pridané: 22.5.2007 18:36 UZ PRESTAN POUZIVAT MOJ NICK Odpovedať Hodnotiť:

O-M-G Od: O-M-G | Pridané: 22.5.2007 18:46 "vyvinutý Arjenom Lenstrom a ďalšími matematikmi na konci 80-tych rokoCH. " POMOOOOOOOC, Hornik je bud vychodnar alebo MADAR! :-((( Odpovedať Hodnotiť:

PH Od: PH | Pridané: 22.5.2007 20:40 dajte si facku! Odpovedať Hodnotiť:

Montano Od: Montano | Pridané: 22.5.2007 20:58 jeb Odpovedať Hodnotiť:

thriler Od: thriler | Pridané: 22.5.2007 21:07 NO tak to vidite ja mam taky program v Pascale za par minut. Akurat mi to take velke cislo nezhltne. :D Odpovedať Hodnotiť:

zippy Od: zippy | Pridané: 24.5.2007 15:49 ano. ale s tym, ze keby ti to aj zozralo, tak ti to nebude ratat 100rokov, ale 1000 - urcite si nepouzil heuristiky, ze? Odpovedať Hodnotiť:

dressler Od: dressler | Pridané: 23.5.2007 7:20 krasne a co sme tym ako ziskali? :D :D :D Odpovedať Hodnotiť:

__KO__ Od: __KO__ | Pridané: 23.5.2007 8:48 Radost z toho ze mozme prelomit 1039 bitove cislo za "100 rokov" vypoctu na PC. Ked daju 2000 Bitove az potom to bude sranda... Odpovedať Hodnotiť:

Bozz Od: Bozz | Pridané: 24.5.2007 19:56 "elliptic curve cryptography" kurva toto ma byt urážka? a do piči aký som najebaný!!!!!!!! Odpovedať Hodnotiť:

nevedko Od: nevedko | Pridané: 26.5.2007 9:57 Zaujímavé je vymyslieť si takú prácu ktorú nikto nechápe a ešte ťa za to aj dobre platia, nikto nevie čo vypočítali, ale 11 mesiacov za to brali plat, a výsledok, sa nedá overiť xixi, skrátka sú šikovný, jedine ak by to Chuck skontroloval tak by mali po piici... Odpovedať Hodnotiť:

Pridať komentár