Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: listoper 24. 09. 2018, 15:56:56
-
Ahoj,
jsou tady nejaci kryptografici? A nebo nadsenci do teorie cisel?
Mozna ste cetli ze Michael Atiyah dnes prezentoval svuj "dukaz".
Ja sem cetl udajny preprint: https://drive.google.com/file/d/17NBICP6OcUSucrXKNWvzLmrQpfUrEKuY/view (https://drive.google.com/file/d/17NBICP6OcUSucrXKNWvzLmrQpfUrEKuY/view)
A mam nekolik otazek:
1. Nazory na ten dukaz? Ja mam urcite pochybnosti (Mozna proto ze jsem necetl vsechny ty reference a hlavne proto ze nejsem matematik :-))
2. Zil jsem v tom, ze dukaz RH bude mit nasledky v kryptografii kvuli snadnemu hledani velkych prvocisel a mozna nalezeni nejake noveho vztahu ktery mezi nimi existuje. Ale tohle je dukaz sporem... Takze to podle me nebude mit primi vliv vlastne na nic. (Jen, pokud to uznaji ostatni hlavy jako dukaz, tak zacnou platit jine dukazy ktere jsou zalozene na predpokladu spravnosti RH). Vidite nekdo nejaky impakt toho dukazu do praxe?
Diky
-
Riemanova hypoteza sa prakticky na ucely distribucie prvocisel prakticky pouziva uz roky. Inzinierska indukcia :) az by sa nasli vynimky, ze niektore nelezi na tej 1/2 tak ich strcime do pola vynimiek a hotovo 8)
-
[quote author=listoper link=topic=19659.msg288463#msg288463 A mam nekolik otazek:
1. Nazory na ten dukaz? Ja mam urcite pochybnosti (Mozna proto ze jsem necetl vsechny ty reference a hlavne proto ze nejsem matematik :-))
[/quote]
Obávám se že to nebude tak horké, tenhle comment na blogu pověstném zveřejňováním drbů mluví za vše. (a PW má M. Atiyaha v dost velké úctě)
http://www.math.columbia.edu/~woit/wordpress/?p=10560&cpage=1#comment-231868
2. Zil jsem v tom, ze dukaz RH bude mit nasledky v kryptografii kvuli snadnemu hledani velkych prvocisel a mozna nalezeni nejake noveho vztahu ktery mezi nimi existuje. Ale tohle je dukaz sporem... Takze to podle me nebude mit primi vliv vlastne na nic. (Jen, pokud to uznaji ostatni hlavy jako dukaz, tak zacnou platit jine dukazy ktere jsou zalozene na predpokladu spravnosti RH). Vidite nekdo nejaky impakt toho dukazu do praxe?
Z laického pohledu mi to připadá, že důkaz RH by v "praxi" způsobil jen to, že by se z pár konjektur staly teorémy. Na druhou stranu pro matematiky by to byl průlom, najednou by automaticky fungovalo spousta důkazů dalších věcí.
-
Riemanova hypoteza sa prakticky na ucely distribucie prvocisel prakticky pouziva uz roky. Inzinierska indukcia :) az by sa nasli vynimky, ze niektore nelezi na tej 1/2 tak ich strcime do pola vynimiek a hotovo 8)
Myslel jsem to spis tak, ze by se nejakym novym objevem, pomoci ktereho by sla dokazat RH, rozbila kryptografie...
Nez ze bysme diky potvrzeni platnosti dostali nejaky novy nastroj.
-
Obávám se že to nebude tak horké, tenhle comment na blogu pověstném zveřejňováním drbů mluví za vše. (a PW má M. Atiyaha v dost velké úctě)
http://www.math.columbia.edu/~woit/wordpress/?p=10560&cpage=1#comment-231868
Dekuju
2. Zil jsem v tom, ze dukaz RH bude mit nasledky v kryptografii kvuli snadnemu hledani velkych prvocisel a mozna nalezeni nejake noveho vztahu ktery mezi nimi existuje. Ale tohle je dukaz sporem... Takze to podle me nebude mit primi vliv vlastne na nic. (Jen, pokud to uznaji ostatni hlavy jako dukaz, tak zacnou platit jine dukazy ktere jsou zalozene na predpokladu spravnosti RH). Vidite nekdo nejaky impakt toho dukazu do praxe?
Z laického pohledu mi to připadá, že důkaz RH by v "praxi" způsobil jen to, že by se z pár konjektur staly teorémy. Na druhou stranu pro matematiky by to byl průlom, najednou by automaticky fungovalo spousta důkazů dalších věcí.
Takze zajimavejsi by vlastne bylo kdyby nekdo dokazal neplatnost. To by se z par konjektur stala sberna surovina. ;D
-
Myslel jsem to spis tak, ze by se nejakym novym objevem, pomoci ktereho by sla dokazat RH, rozbila kryptografie...
To ani nahodou. Vdaka RT sme nasli triliony prvocisel, to ci bude dokazana alebo nie nemeni nic na fakte ze “funguje”. RT len zuzuje stavovy priestor kde dalsie prvocislo hladat. Kryptografia zacina az tam, ze ako tie prvocisla v algoritme pouzijes, a je viacmenej jedno ci pouzivas uz objavene alebo neobjavene prvocisla.
-
Myslel jsem to spis tak, ze by se nejakym novym objevem, pomoci ktereho by sla dokazat RH, rozbila kryptografie...
To ani nahodou. Vdaka RT sme nasli triliony prvocisel, to ci bude dokazana alebo nie nemeni nic na fakte ze “funguje”. RT len zuzuje stavovy priestor kde dalsie prvocislo hladat. Kryptografia zacina az tam, ze ako tie prvocisla v algoritme pouzijes, a je viacmenej jedno ci pouzivas uz objavene alebo neobjavene prvocisla.
Ačkoliv v zásadě souhlasím, tak "ani náhodou" je natolik kategorické prohlášení, že bych si dovolil nesouhlasit s tím, že by zpřesnění znalostí o prvočíslech a o dosud skrytých zákonitostech, nemohlo (třeba náhodou) některá šifrovací schémata alespoň oslabit, když tedy ne rovnou rozbít, pokud jsou založená na předpokladech, která poté už nebudou mít takovou váhu.
-
Ten dukaz je z nejvetsi pravdepodobnosti chybny. Aktualni stav Riemannovy hypotezy je, ze se nevi, jak na to. Analogie je treba Fermatova veta.
V 19. stoleti se postupne dokazovalo pro ruzna n (prvocisla), ale ne vsechna n>2 a nakonec se uvazlo na mrtvem bode. Az nekdy v 60. letech s vyzkumem v teorii cisel prisli s Tanijama-Simurovou domenkou a o 20 let pozdeji nekdo prisel s tim, ze Fermatova veta je dusledek teto hypotezy.
Riemannova hypoteza bude neco podobneho. Rozhodne to nebude dukaz na 2 stranky a treba se ani nedockame v tomhle stoleti.
-
Kryptografia zacina az tam, ze ako tie prvocisla v algoritme pouzijes, a je viacmenej jedno ci pouzivas uz objavene alebo neobjavene prvocisla.
Není to tak dlouho, co někde sebrali asi milion veřejných klíčů, a jednoduchým starověkým algoritmem pro nalezení společného dělitele snad polovinu z nich rozlouskli. Vlastně by k tomu stačilo dost velké kuličkové počítadlo! Takže použití již objeveného prvočísla je stoprocentní záruka průseru!
-
Kryptografia zacina az tam, ze ako tie prvocisla v algoritme pouzijes, a je viacmenej jedno ci pouzivas uz objavene alebo neobjavene prvocisla.
Není to tak dlouho, co někde sebrali asi milion veřejných klíčů, a jednoduchým starověkým algoritmem pro nalezení společného dělitele snad polovinu z nich rozlouskli. Vlastně by k tomu stačilo dost velké kuličkové počítadlo! Takže použití již objeveného prvočísla je stoprocentní záruka průseru!
A ty si myslis ze pri kazdem ssh handshake se pocita dosud nezname prvocislo nebo co ? Jasne ze se pouzivaji zname, ty akorat nevis ktere byli vzaty pri faktorizaci a jak byly osoleny. Brute force to muzes louskat do aleluja. Tvuj priklad je k slabemu algoritmu.
-
Vážení spolubojovníci na poli IT. Včera jsem se dočetl, že Riemannova hypotéza byla dokázána. Po 160 letech. Co myslíte, jaký bude dopad na šifrologii? Jedním z důsledků je třebas zpočitatelnost prvočísel od-do. Nevzniknou nové šifrovací algoritmy? Anebo odlehčeně: nechá si Apple zase patentovat nějakou ptákovinu z důkazu vyplývající? Hezký den a nezlobte se na nadhozenou rozpravu.
-
Jestli byla dokázána, nebo ne se ještě neví. A pravděpodobně chvíli ještě nebude. Jinak je tu na toto téma už téma založené, tak by bylo fajn psát tam.
-
Kryptografia zacina az tam, ze ako tie prvocisla v algoritme pouzijes, a je viacmenej jedno ci pouzivas uz objavene alebo neobjavene prvocisla.
Není to tak dlouho, co někde sebrali asi milion veřejných klíčů, a jednoduchým starověkým algoritmem pro nalezení společného dělitele snad polovinu z nich rozlouskli. Vlastně by k tomu stačilo dost velké kuličkové počítadlo! Takže použití již objeveného prvočísla je stoprocentní záruka průseru!
A ty si myslis ze pri kazdem ssh handshake se pocita dosud nezname prvocislo nebo co ? Jasne ze se pouzivaji zname, ty akorat nevis ktere byli vzaty pri faktorizaci a jak byly osoleny. Brute force to muzes louskat do aleluja. Tvuj priklad je k slabemu algoritmu.
1) Veřejné klíče jsou veřejné.
2) Z milionu klíčů cca polovina měla shodné minimálně jedno prvočíslo s jiným.
3) Tak si klidně sypej sůl do očí.
-
(https://i.imgflip.com/rmmn3.jpg)
-
Kryptografia zacina az tam, ze ako tie prvocisla v algoritme pouzijes, a je viacmenej jedno ci pouzivas uz objavene alebo neobjavene prvocisla.
Není to tak dlouho, co někde sebrali asi milion veřejných klíčů, a jednoduchým starověkým algoritmem pro nalezení společného dělitele snad polovinu z nich rozlouskli. Vlastně by k tomu stačilo dost velké kuličkové počítadlo! Takže použití již objeveného prvočísla je stoprocentní záruka průseru!
muzes mi dat nejaky hint kde se da najit clanek
-
Riemannova hypoteza nebyla dokazana, dukaz je temer urcite chybny. Atiyahovi je pres 90 a pravdepodobne trpi stareckou demenci, takze tak.
Znam to od otce (byl fyzik) - u vysoce inteligentnich lidi to skoro na prvni pohled neni poznat. Ukladani do dlouhodobe pameti odchazi jako prvni, a jelikoz inteligentni lide vedi spoustu veci, dokazi tenhle nedostatek velice dobre maskovat.
Muj tata jeste nekolik let pote, co jsme ho podezirali z demence, byl schopen treba psat v TeXu na pocitaci (editoval nove vydani sve knihy, ktera nakonec vysla tesne pred jeho smrti s pomoci jeho kolegy). Nastesti si aspon nemyslel, ze objevil neco noveho.
-
Riemannova hypoteza nebyla dokazana, dukaz je temer urcite chybny. Atiyahovi je pres 90 a pravdepodobne trpi stareckou demenci, takze tak.
Znam to od otce (byl fyzik) - u vysoce inteligentnich lidi to skoro na prvni pohled neni poznat. Ukladani do dlouhodobe pameti odchazi jako prvni, a jelikoz inteligentni lide vedi spoustu veci, dokazi tenhle nedostatek velice dobre maskovat.
Muj tata jeste nekolik let pote, co jsme ho podezirali z demence, byl schopen treba psat v TeXu na pocitaci (editoval nove vydani sve knihy, ktera nakonec vysla tesne pred jeho smrti s pomoci jeho kolegy). Nastesti si aspon nemyslel, ze objevil neco noveho.
Naopak porušená paměť vás může posunout do jiného způsobu uvažování, a právě díky ní, může být vidět řešení, které je s dokonalou pamětí nedostupné. Bohužel člověk je zajatcem vlastních stereotypů. Proto pokud něco nevymyslí do 25, pak už to nevymyslí, protože jeho mysl je už nasměrovaná a je více méně náhoda na co po cestě uvidí a na co narazí.
Degradace mozku a jeho rekonfigurace vás může nasměrovat jiným, třeba perspektivnějším směrem. Tipl bych si, že autor to řešení uviděl najednou a nečekaně. Nebylo výsledkem vědomého procesu hledání.
-
Riemannova hypoteza nebyla dokazana, dukaz je temer urcite chybny. Atiyahovi je pres 90 a pravdepodobne trpi stareckou demenci, takze tak.
Znam to od otce (byl fyzik) - u vysoce inteligentnich lidi to skoro na prvni pohled neni poznat. Ukladani do dlouhodobe pameti odchazi jako prvni, a jelikoz inteligentni lide vedi spoustu veci, dokazi tenhle nedostatek velice dobre maskovat.
Muj tata jeste nekolik let pote, co jsme ho podezirali z demence, byl schopen treba psat v TeXu na pocitaci (editoval nove vydani sve knihy, ktera nakonec vysla tesne pred jeho smrti s pomoci jeho kolegy). Nastesti si aspon nemyslel, ze objevil neco noveho.
Naopak porušená paměť vás může posunout do jiného způsobu uvažování, a právě díky ní, může být vidět řešení, které je s dokonalou pamětí nedostupné. Bohužel člověk je zajatcem vlastních stereotypů. Proto pokud něco nevymyslí do 25, pak už to nevymyslí, protože jeho mysl je už nasměrovaná a je více méně náhoda na co po cestě uvidí a na co narazí.
Degradace mozku a jeho rekonfigurace vás může nasměrovat jiným, třeba perspektivnějším směrem. Tipl bych si, že autor to řešení uviděl najednou a nečekaně. Nebylo výsledkem vědomého procesu hledání.
Ale pravdepodobnost, ze se takto slozity problem vyresi nejakym trikem je minimalni. To uz by se nekdo nasel.
-
Riemannova hypoteza nebyla dokazana, dukaz je temer urcite chybny. Atiyahovi je pres 90 a pravdepodobne trpi stareckou demenci, takze tak.
Znam to od otce (byl fyzik) - u vysoce inteligentnich lidi to skoro na prvni pohled neni poznat. Ukladani do dlouhodobe pameti odchazi jako prvni, a jelikoz inteligentni lide vedi spoustu veci, dokazi tenhle nedostatek velice dobre maskovat.
Muj tata jeste nekolik let pote, co jsme ho podezirali z demence, byl schopen treba psat v TeXu na pocitaci (editoval nove vydani sve knihy, ktera nakonec vysla tesne pred jeho smrti s pomoci jeho kolegy). Nastesti si aspon nemyslel, ze objevil neco noveho.
Naopak porušená paměť vás může posunout do jiného způsobu uvažování, a právě díky ní, může být vidět řešení, které je s dokonalou pamětí nedostupné. Bohužel člověk je zajatcem vlastních stereotypů. Proto pokud něco nevymyslí do 25, pak už to nevymyslí, protože jeho mysl je už nasměrovaná a je více méně náhoda na co po cestě uvidí a na co narazí.
Degradace mozku a jeho rekonfigurace vás může nasměrovat jiným, třeba perspektivnějším směrem. Tipl bych si, že autor to řešení uviděl najednou a nečekaně. Nebylo výsledkem vědomého procesu hledání.
No podle toho co rikal tak vubec nehledal dukaz RH. On resil tu Todd fci kvuli kvantove fyzice. A jen tak mimochodem si pry uvedomil, ze vlastne lze pouzit k dukazu RH.
-
Ano a šel na to fintou. Místo toho aby se snažil dokázat že reálné části výsledku jsou vždy 1/2, tak to zkusil dokázat rozporem. Zkusil dokázat že reálné části leží v intervalu 0 až 1 - a důkaz nevyšel, neboť lze dokázat že existují množiny v tomto intervalu, které nevyhovuji Riemannovi. Já jsem sice houby matematik, ale protože 1/2 je součástí intervalu (0 - 1), tak mu ten rozporný důkaz měl vyjít. Tudíž se nemusíme obávat vlivu na šifrování :-)
-
Ano a šel na to fintou. Místo toho aby se snažil dokázat že reálné části výsledku jsou vždy 1/2, tak to zkusil dokázat rozporem. Zkusil dokázat že reálné části leží v intervalu 0 až 1 - a důkaz nevyšel, neboť lze dokázat že existují množiny v tomto intervalu, které nevyhovuji Riemannovi. Já jsem sice houby matematik, ale protože 1/2 je součástí intervalu (0 - 1), tak mu ten rozporný důkaz měl vyjít. Tudíž se nemusíme obávat vlivu na šifrování :-)
To je trochu pomotane. To, ze nuly jsou vsechny krom trivialnich v kritickem pasu uz dokazal snad sam Riemann. On zalozil ten spor na existenci nuly v kritickem pasu ale mimo 1/2. Coz je v poradku. Problem je podle me v te kompozici s Todd.
-
Riemannova hypoteza nebyla dokazana, dukaz je temer urcite chybny. Atiyahovi je pres 90 a pravdepodobne trpi stareckou demenci, takze tak.
Znam to od otce (byl fyzik) - u vysoce inteligentnich lidi to skoro na prvni pohled neni poznat. Ukladani do dlouhodobe pameti odchazi jako prvni, a jelikoz inteligentni lide vedi spoustu veci, dokazi tenhle nedostatek velice dobre maskovat.
Muj tata jeste nekolik let pote, co jsme ho podezirali z demence, byl schopen treba psat v TeXu na pocitaci (editoval nove vydani sve knihy, ktera nakonec vysla tesne pred jeho smrti s pomoci jeho kolegy). Nastesti si aspon nemyslel, ze objevil neco noveho.
Naopak porušená paměť vás může posunout do jiného způsobu uvažování, a právě díky ní, může být vidět řešení, které je s dokonalou pamětí nedostupné. Bohužel člověk je zajatcem vlastních stereotypů. Proto pokud něco nevymyslí do 25, pak už to nevymyslí, protože jeho mysl je už nasměrovaná a je více méně náhoda na co po cestě uvidí a na co narazí.
Degradace mozku a jeho rekonfigurace vás může nasměrovat jiným, třeba perspektivnějším směrem. Tipl bych si, že autor to řešení uviděl najednou a nečekaně. Nebylo výsledkem vědomého procesu hledání.
Ale pravdepodobnost, ze se takto slozity problem vyresi nejakym trikem je minimalni. To uz by se nekdo nasel.
Nenašel, většina lidí uvažuje jako vy, jen demence může poškodit právě tu část mozku, která je zodpovědná za vámi předvedený typ uvažování.
-
Riemannova hypoteza nebyla dokazana, dukaz je temer urcite chybny. Atiyahovi je pres 90 a pravdepodobne trpi stareckou demenci, takze tak.
Znam to od otce (byl fyzik) - u vysoce inteligentnich lidi to skoro na prvni pohled neni poznat. Ukladani do dlouhodobe pameti odchazi jako prvni, a jelikoz inteligentni lide vedi spoustu veci, dokazi tenhle nedostatek velice dobre maskovat.
Muj tata jeste nekolik let pote, co jsme ho podezirali z demence, byl schopen treba psat v TeXu na pocitaci (editoval nove vydani sve knihy, ktera nakonec vysla tesne pred jeho smrti s pomoci jeho kolegy). Nastesti si aspon nemyslel, ze objevil neco noveho.
Naopak porušená paměť vás může posunout do jiného způsobu uvažování, a právě díky ní, může být vidět řešení, které je s dokonalou pamětí nedostupné. Bohužel člověk je zajatcem vlastních stereotypů. Proto pokud něco nevymyslí do 25, pak už to nevymyslí, protože jeho mysl je už nasměrovaná a je více méně náhoda na co po cestě uvidí a na co narazí.
Degradace mozku a jeho rekonfigurace vás může nasměrovat jiným, třeba perspektivnějším směrem. Tipl bych si, že autor to řešení uviděl najednou a nečekaně. Nebylo výsledkem vědomého procesu hledání.
No podle toho co rikal tak vubec nehledal dukaz RH. On resil tu Todd fci kvuli kvantove fyzice. A jen tak mimochodem si pry uvedomil, ze vlastne lze pouzit k dukazu RH.
No právě, to je přesně ono. Viděl něco, co jiní nemají možnost uvidět, protože nemají vhodně "poškozený" mozek.
-
https://www.johndcook.com/blog/2018/09/24/riemann-hypothesis-the-fine-structure-constant-and-the-todd-function/
Pry uz delal chyby v poslednich letech, navic mu zemrela manzelka, je mu 90 let...
-
Není to tak dlouho, co někde sebrali asi milion veřejných klíčů, a jednoduchým starověkým algoritmem pro nalezení společného dělitele snad polovinu z nich rozlouskli. Vlastně by k tomu stačilo dost velké kuličkové počítadlo! Takže použití již objeveného prvočísla je stoprocentní záruka průseru!
IIRC to bylo řádově méně (2.5 %?), navíc se jednalo převážně o klíče generované na embedded a jiných malých zařízeních s nedostatkem entropie.
Jedním z důsledků je třebas zpočitatelnost prvočísel od-do
Pokud se ten počet neliší od našich dosavadních odhadů o mnoho řádů, tak u nejpoužívanějších schémat nevidím problém. Těch prvočísel je v intervalech, ze kerých se "vybírají" prostě příliš mnoho, ať již ten počet známe přesně či ne.
-
Pry uz delal chyby v poslednich letech, navic mu zemrela manzelka, je mu 90 let...
Vy mu ten dukaz snad neprejete nebo co ? Vedecka metoda je o dukazech a skepsa je emoce a ne racionalno :D Kdyz ma dukaz a nenajde se v nem dira ci vyvraceni tak ma dukaz a basta.
-
Vy mu ten dukaz snad neprejete nebo co ? Vedecka metoda je o dukazech a skepsa je emoce a ne racionalno :D Kdyz ma dukaz a nenajde se v nem dira ci vyvraceni tak ma dukaz a basta.
To je dost odvážné tvrzení, řekl bych až nefungující. Viz velmi nešťastná situace kolem abc konjektury, když už jsme u těžkých matematických problémů.
-
Pry uz delal chyby v poslednich letech, navic mu zemrela manzelka, je mu 90 let...
Vy mu ten dukaz snad neprejete nebo co ? Vedeceka metoda je o dukazech a skepsa je emoce a ne racionalno :D Kdyz ma dukaz a nenajde se v nem dira ci vyvraceni tak ma dukaz a basta.
Nepreju, protoze to neprinasi vhled do distribuce prvocisel. :-*
-
Podivejte se treba na jeho prednasku v lete v Riu (youtube). To, myslim, hovori za vse.
-
Podivejte se treba na jeho prednasku v lete v Riu (youtube). To, myslim, hovori za vse.
Mozes byt konkretnejsi? Nie kazdy tu ma cas hladat prednasky v Riu. A ak nieco nevies povedat jednym rozvitym suvetim tak radsej nehovor nic.
-
lubos motl
https://motls.blogspot.com/2018/09/nice-try-but-i-am-now-99-confident-that.html?m=1
-
Myslel jsem to spis tak, ze by se nejakym novym objevem, pomoci ktereho by sla dokazat RH, rozbila kryptografie...
Nez ze bysme diky potvrzeni platnosti dostali nejaky novy nastroj.
Jenze ty tady tu hypotezu mas, takze ji prakticky pouzivat muzes, jen si nemuzes byt jisty tim, ze plati zcela vzdy, ale klidne ji tak muzes pouzit.
Takze dusledky by byly spis nulovy.
Je to uplne stejny, jako kdyz prohlasim, ze zitra vyjde slunce. Taky vyjit nemusi, muze treba vybouchnout ... ale vsichni predpokladaji, ze vyjde.
... Rozhodne to nebude dukaz na 2 stranky ...
Tak tohle je oblybeny omyl, vetsina veci se da dokazat i na min nez jedny strance. Jen to vedci velmi neradi prijimaji, prirodni zakony (a matematika k nim patri) proste jsou jednoduchy, coz neznamena ze je jednoduse chapeme.
...Takže použití již objeveného prvočísla je stoprocentní záruka průseru!
Tusis ty vubec jak ty veci fungujou? Zadna jina prvocisla se nepouzivaji. Jak bys chtel pouzit neznamy provocislo probuh? To bys jako na konexi ke zminenymu sshcku cekal rok?
-
Myslel jsem to spis tak, ze by se nejakym novym objevem, pomoci ktereho by sla dokazat RH, rozbila kryptografie...
Nez ze bysme diky potvrzeni platnosti dostali nejaky novy nastroj.
Jenze ty tady tu hypotezu mas, takze ji prakticky pouzivat muzes, jen si nemuzes byt jisty tim, ze plati zcela vzdy, ale klidne ji tak muzes pouzit.
Takze dusledky by byly spis nulovy.
Je to uplne stejny, jako kdyz prohlasim, ze zitra vyjde slunce. Taky vyjit nemusi, muze treba vybouchnout ... ale vsichni predpokladaji, ze vyjde.
Hmm tak budu muset vysvetlit vysvetleni. Ja se fakt asi neumim vyjadrit :-).
Zkusim na to pouzit priklad:
Co kdyz by nekdo k dukazu RH pouzil nove objeveneho vztahu mezi prvocisly? (Jinak receno, nejen by potvrdil, ze jsou nuly v 1/2, ale taky vymyslel proc...)
Treba by nasel vzorec kde z 3 posobe nasledujicich prvocisel odvodim ctvrte, nebo by objevil univerzalni vzorec na vypocet n-teho prvocisla pouze pomoci "n", a nebo (a ted uz hodne prehanim ) by si vsimnul toho, ze prvocisla jsou vlastne vsechny beze zbytku delitelny dvema, jen si toho doted nikdo nevsiml....
Takovy objev by prece snizil vypocetni slozitost uloh s prvocisly. A tudiz by mohl oslabit nektere kryptograficke mechanismy.
A ja tak nejak cekam(nebo aspon doufam), ze jestli se nekdy objevi opravdovy dukaz RH tak to bude dukaz tohoto typu.
-
...
A k cemu by ti to bylo? Kdyz pouzivas sifrovani, tak vzdy pouzijes predem znama prvocisla. Takze to ze umis lusknutim prstu najit dalsi a dalsi prvocisla (coz ted neumis) na tom nijak nic nezmeni. Ty bys musel najit nejakej postup, jak z toho vyslednyho zasifrovance urcit ta pouzita (a z nich pripadne dopocitat klic).
Tzn rekneme ze bys zjistil, ze soucin kazdych dvou prvocisel je zase prvocislo ... a to navic vzdy unikatni pro konkretni cinitele. Pak by sifrovani slo samo do rite.
Mimochodem, i proto je elektronicky podpis naprosta chymera a hovadina, protoze se zcela kdykoli muze stat, ze nekdo najde zcela primitivni postup jak algoritmus zbourat. A to plati i v horizontu mesicu, natoz let.
-
...
A k cemu by ti to bylo? Kdyz pouzivas sifrovani, tak vzdy pouzijes predem znama prvocisla. Takze to ze umis lusknutim prstu najit dalsi a dalsi prvocisla (coz ted neumis) na tom nijak nic nezmeni. Ty bys musel najit nejakej postup, jak z toho vyslednyho zasifrovance urcit ta pouzita (a z nich pripadne dopocitat klic).
Tzn rekneme ze bys zjistil, ze soucin kazdych dvou prvocisel je zase prvocislo ... a to navic vzdy unikatni pro konkretni cinitele. Pak by sifrovani slo samo do rite.
Myslim, ze sam odpovidas na otazku "k cemu by ti to bylo?" v tom nasledujicim prikladu.
Treba uz by stacilo jen kdyby se nam podarilo klasifikovat nejake skupiny prvocisel ke konkretnimu zasifrovanci a zmensit tak mnozinu ve ktere musim ty konkretni cisla hledat.
-
Treba uz by stacilo jen kdyby se nam podarilo klasifikovat nejake skupiny prvocisel ke konkretnimu zasifrovanci a zmensit tak mnozinu ve ktere musim ty konkretni cisla hledat.
Kurna po 151. opakuji ze to muzes udelat i hned. RH funguje, to ze neni dokazana tomu nijak nebrani. Kdyz ji dokazou tak jen potvrdi co uz davno vime. Kdyz ji vyvrati tak pridame nejake vyjimky a jde se dal.
-
:D
;D ;D
:P :P :P
;D ;D
:D
:D
;D ;D
:P :P :P
;D ;D
:D
:D
;D ;D
:P :P :P
;D ;D
:D
-
...
Kurna po 151. opakuji ze to muzes udelat i hned. RH funguje, to ze neni dokazana tomu nijak nebrani. Kdyz ji dokazou tak jen potvrdi co uz davno vime. Kdyz ji vyvrati tak pridame nejake vyjimky a jde se dal.
Tak nejak ... apropos, mas program na zejtra? A co kdyz zadny zejtra nebude? Nikdo totiz jeste nedokazal, ze nejaky zejtra bude.
-
Treba uz by stacilo jen kdyby se nam podarilo klasifikovat nejake skupiny prvocisel ke konkretnimu zasifrovanci a zmensit tak mnozinu ve ktere musim ty konkretni cisla hledat.
Kurna po 151. opakuji ze to muzes udelat i hned. RH funguje, to ze neni dokazana tomu nijak nebrani. Kdyz ji dokazou tak jen potvrdi co uz davno vime. Kdyz ji vyvrati tak pridame nejake vyjimky a jde se dal.
Ale ja prece nerikam, ze nefunguje.
Ani nerikam, ze ten dukaz jako takovy bude mit vliv na krypto....
Ja rikam, ze jsem cekal ze dukaz bude proveden diky novemu objevu vztahu nebo vlastnosti prvocisel.
A ten vztah nebo vlastnost bude mit vliv na krypto...
A to dneska prece pouzit nemuzu, protoze to jeste nebylo objeveno...
-
...
Kurna po 151. opakuji ze to muzes udelat i hned. RH funguje, to ze neni dokazana tomu nijak nebrani. Kdyz ji dokazou tak jen potvrdi co uz davno vime. Kdyz ji vyvrati tak pridame nejake vyjimky a jde se dal.
Tak nejak ... apropos, mas program na zejtra? A co kdyz zadny zejtra nebude? Nikdo totiz jeste nedokazal, ze nejaky zejtra bude.
Ja sem to dokazal. Zejtra bude. Jestli chces tak ten dukaz zejtra ukazu :-) Dneska uz na to nebudu mit cas...
-
Ja rikam, ze jsem cekal ze dukaz bude proveden diky novemu objevu vztahu nebo vlastnosti prvocisel.
A ten vztah nebo vlastnost bude mit vliv na krypto...
A to dneska prece pouzit nemuzu, protoze to jeste nebylo objeveno...
Jakemu novem vztahu? Ten vzah je 160 let starej, nic nove se neresi jen se ceka ze v knizkach skrtneme slovo hypoteza a prepisme na veta.
-
Ja rikam, ze jsem cekal ze dukaz bude proveden diky novemu objevu vztahu nebo vlastnosti prvocisel.
A ten vztah nebo vlastnost bude mit vliv na krypto...
A to dneska prece pouzit nemuzu, protoze to jeste nebylo objeveno...
Jakemu novem vztahu? Ten vzah je 160 let starej, nic nove se neresi jen se ceka ze v knizkach skrtneme slovo hypoteza a prepisme na veta.
No to asi nemuzu ted rict jakymu novymu vztahu kdyz pisu ze jeste neni objevenej...
Riemann si vsimnul ze se neco deje, a protoze se to tak delo pro vsechny pripady, ktere videl tak se "domnival" ze se to tak deje vzdycky. Ale nikdo nevi proc to tak je. A ten duvod proc to tak je, muze byt objeven a muze zpusobit 1) dukaz RH 2) zkazu kryptografie...
Dukaz muze byt ruzneho druhu. Treba sporem jak je tomu v pripade toho pokusu pana Athiyaha. Pak se zadny novy objev(vztahu nabo vlastnosti) konat nebude a krypto muze byt v klidu.
Ale ja se domnivam (jak uz jsem psal), ze dukaz RH bude (jestli nekdy bude) proveden pomoci nejakeho toho nove objeveneho vztahu nebo vlastnosti.
-
Ja rikam, ze jsem cekal ze dukaz bude proveden diky novemu objevu vztahu nebo vlastnosti prvocisel.
A ten vztah nebo vlastnost bude mit vliv na krypto...
A to dneska prece pouzit nemuzu, protoze to jeste nebylo objeveno...
Jakemu novem vztahu? Ten vzah je 160 let starej, nic nove se neresi jen se ceka ze v knizkach skrtneme slovo hypoteza a prepisme na veta.
No to asi nemuzu ted rict jakymu novymu vztahu kdyz pisu ze jeste neni objevenej...
Riemann si vsimnul ze se neco deje, a protoze se to tak delo pro vsechny pripady, ktere videl tak se "domnival" ze se to tak deje vzdycky. Ale nikdo nevi proc to tak je. A ten duvod proc to tak je, muze byt objeven a muze zpusobit 1) dukaz RH 2) zkazu kryptografie...
Dukaz muze byt ruzneho druhu. Treba sporem jak je tomu v pripade toho pokusu pana Athiyaha. Pak se zadny novy objev(vztahu nabo vlastnosti) konat nebude a krypto muze byt v klidu.
Ale ja se domnivam (jak uz jsem psal), ze dukaz RH bude (jestli nekdy bude) proveden pomoci nejakeho toho nove objeveneho vztahu nebo vlastnosti.
Zkazu asi ne. Precti si poradne ten Riemanuv originalni paper. Co vlastne zjistil :)
-
Ja rikam, ze jsem cekal ze dukaz bude proveden diky novemu objevu vztahu nebo vlastnosti prvocisel.
A ten vztah nebo vlastnost bude mit vliv na krypto...
Jinými slovy, předpokládal jste, že ten důkaz nebo něco, co k němu povede, bude ještě silnější, než Riemannova hypotéza, a to, co tam bude navíc oproti R. hypotéze, bude mít vliv na kryptografii založené na prvočíslech. Je to tak?
-
Ja rikam, ze jsem cekal ze dukaz bude proveden diky novemu objevu vztahu nebo vlastnosti prvocisel.
A ten vztah nebo vlastnost bude mit vliv na krypto...
Jinými slovy, předpokládal jste, že ten důkaz nebo něco, co k němu povede, bude ještě silnější, než Riemannova hypotéza, a to, co tam bude navíc oproti R. hypotéze, bude mít vliv na kryptografii založené na prvočíslech. Je to tak?
Nevim jestli se da tady hodnotit co je silnejsi nebo slabsi...
Ale jinak ano.
-
Nevim jestli se da tady hodnotit co je silnejsi nebo slabsi...
Silnější ve smyslu „dokazuje to víc“, „více to omezuje výslednou množinu nebo podrobněji specifikuje, kde prvočísla hledat“, „můžeme na základě toho dělat silnější předpoklady“.
-
Nevim jestli se da tady hodnotit co je silnejsi nebo slabsi...
Silnější ve smyslu „dokazuje to víc“, „více to omezuje výslednou množinu nebo podrobněji specifikuje, kde prvočísla hledat“, „můžeme na základě toho dělat silnější předpoklady“.
Tak jo. Takhle ano. Doufam v uplne pochopeni distribuce prvocisel takze nejsilnejsi :-)
-
Poněkud mě překvapila hypotéza, že se pro kryptografii používají známá prvočísla. Předpokládám, že tím bylo myšleno RSA, které je asi nejpopulárnějším kryptoalgoritmem založeným na prvočíslech a kde je případný snadný prvočíselný rozklad problémem. Jenže tam případná znalost jednoho z prvočísel útočníkem je průšvih samo o sobě.
Co si vzpomínám, tak se běžně používají na hledání prvočísel různé triky, takže se nepoužije celý ≈ 2^1014 prostor pro prvočísla k RSA-2048, ale jen nějaký zúžený. Alr i ten zúžený může být pořád dost velký. Konkrétní varianta zjednodušení může mít nějaké zranitelnosti (vzpomeňme si na ROCA), případně nějaké charakteristiky (tým zabývající se ROCA předtím AFAIR dovedl odhadnout, čím byl daný klíč vygenerován).
Jestli případný důkaz pomůže omezit prostor, kde hledat jedno z těch prvočísel – asi moc ne. Velikost toho prostoru těžko bude převapením pro lidi, kteří řeší to hledání prvočísel, ono se to zákonitě musí nějak projevit do statistik, za jak dlouho to prvočíslo najdu. Což má vliv i na výkon.
Jestli případný důkaz přinese něco jiného, co nám zboří RSA nebo jinou část kryptografie – to je tak obecná otázka, že by bylo pošetilé odpovídat jednoznačně „ne“. Ale nějaký velký strach z toho nemám.
-
Co napsal Vít dává smysl.
O prvočíslech toho moc nevíme, jejich zastoupení je třeba přibližně definované přirozeným logaritmem a v případě, kdy bychom dopředu věděli, která čísla jsou prvočísly, můžeme snížit náročnost RSA 2048 o spousty řádů, v tom tkví dokázání téhle hypotézy.
Co je ale vtipné, pokud se prokáže, že tenhle důkaz sporem je správný, nevypadá to, že by se něco s kryptografií prvočísel stalo, pořád nemáme "funkci na prvočísla" a musíme je hledat hrubou silou.
-
Co napsal Vít dává smysl.
O prvočíslech toho moc nevíme, jejich zastoupení je třeba přibližně definované přirozeným logaritmem a v případě, kdy bychom dopředu věděli, která čísla jsou prvočísly, můžeme snížit náročnost RSA 2048 o spousty řádů, v tom tkví dokázání téhle hypotézy.
Co je ale vtipné, pokud se prokáže, že tenhle důkaz sporem je správný, nevypadá to, že by se něco s kryptografií prvočísel stalo, pořád nemáme "funkci na prvočísla" a musíme je hledat hrubou silou.
tady píšou, že je těch prvočísel fakt hodně https://stackoverflow.com/questions/16091581/how-many-prime-numbers-are-there-available-for-rsa-encryption
-
Poněkud mě překvapila hypotéza, že se pro kryptografii používají známá prvočísla. Předpokládám, že tím bylo myšleno RSA, které je asi nejpopulárnějším kryptoalgoritmem založeným na prvočíslech a kde je případný snadný prvočíselný rozklad problémem. Jenže tam případná znalost jednoho z prvočísel útočníkem je průšvih samo o sobě.
Co si vzpomínám, tak se běžně používají na hledání prvočísel různé triky, takže se nepoužije celý ≈ 2^1014 prostor pro prvočísla k RSA-2048, ale jen nějaký zúžený. Alr i ten zúžený může být pořád dost velký. Konkrétní varianta zjednodušení může mít nějaké zranitelnosti (vzpomeňme si na ROCA), případně nějaké charakteristiky (tým zabývající se ROCA předtím AFAIR dovedl odhadnout, čím byl daný klíč vygenerován).
Jestli případný důkaz pomůže omezit prostor, kde hledat jedno z těch prvočísel – asi moc ne. Velikost toho prostoru těžko bude převapením pro lidi, kteří řeší to hledání prvočísel, ono se to zákonitě musí nějak projevit do statistik, za jak dlouho to prvočíslo najdu. Což má vliv i na výkon.
Jestli případný důkaz přinese něco jiného, co nám zboří RSA nebo jinou část kryptografie – to je tak obecná otázka, že by bylo pošetilé odpovídat jednoznačně „ne“. Ale nějaký velký strach z toho nemám.
Ne, u RSA se predem znama prvocisla fakt pouzivat nedaji, protoze RSA visi na neznalosti rychleho algoritmu na faktorizaci. Predem znama prvocisla se pouzivaji treba u DH, kde je prvocislo verejne zname. Prvocislo vhodne pro DH musi mit i dalsi vlastnosti nez je jen prvociselnost, takze je i v zasade nezadouci, aby si kazdy generoval svoje. Pro zajimavost, SSH je ma ulozene ponkretne v /etc/ssh/moduli.
-
Kdybychom mohli projít seznam prvočísel rychle (ve smyslu máme vzoreček pro výpočet příštího prvočísla vyčíslitelný za pár taktů CPU), ještě to nic neznamená. Když budu uvažovat RSA-2048, mám 2048b modulus, který je součinem dvou prvočísel o délce cca 1024b. Počet prvočísel zde lze odhadnout na 2^1024/(ln(2^1024)-1), což mi kalkulačka nepobrala, ale dá se to zjednodušit, že cca každé (ln(2^1024)-1)-té číslo v tomto intervalu je prvočíslo. Sice ani ln(2^1024)-1 mi kalkulačka nepobrala, ale když jsem to zjednodušil na 1024*ln(2)-1, dostal jsem, že cca jedno ze 709 čísel je v tomto intervalu prvočíslo. To jsem zaokrouhlil na 1024 a došel jsem k výše uvedenému odhadu 2^(1024-10)=2^1014 prvočísel v tomto intervalu. Řekl bych, že ani dnes není problém v tom, že bychom neuměli dostatečně rychle prvočísla procházet, jako spíš s tím, že je jich prostě moc. Hrubou silou to při jakkoli efektivním způsobu procházení prostě neprojdete. Pro srovnání: AES staví mj. na tom, že neprojdete všech jeho 2^128 až 2^256 (podle varianty) klíčů. To je o poznání méně než počet prvočísel v uvažovaném rozsahu.
Jestli to zefektivní nějaký jiný algoritmus lámání RSA – možná ano, čekal bych ale spíše zlepšení nějakých faktorů, rozhodně ale od toho nečekám polynomiální složitost. Prakticky to znamená, že čekám spíše přinejhorším nutnost používat delší klíče v RSA než kompletní průlom RSA.
A i kdybychom měli průlom RSA, není to dnes nenahraditelný algoritmus… Náhrady se hledají asi spíše z jiných důvodů – rychlost, délka klíče nutná k zajištění dané úrovně bezpečnosti a kvantové počítače.
s: Ale vždyť to používání známých prvočísel vyvracím.
-
btw, nejdelsi zname prvocislo ma pres 23 milionu cislic a pro pouziti v kryptografii uz nejsou takto velka cisla prakticka..
-
Jak to bylo s tím rozluštěním sovětských depeší, šifrovaných Vernamovou šifrou? Stačilo prostě dost dlouho počkat a všechny si je uložit. :-X
kdy bychom dopředu věděli, která čísla jsou prvočísly,
To je právě ten problém. Hledání vhodných prvočísel při výrobě klíčů je velmi náročné, zdaleka ne všechna se dají použít, tak jsou na to různé urychlující zkratky. A občas se tak prostě stane, že se trefí do stejného prvočísla, které se tím použíje ve dvou klíčích. Když potom někdo sesbírá hodně veřejných klíčů, tak má slušnou šanci že v některých z nich nějaké takové bude. A o faktorizaci se v tomhle případě kdysi dávno postaral nějaký pan Euklides. Obyčejným vydělením se potom zjistí i ta unikátní, a najednou je z toho pomalu rostoucí seznam, stačí jen neustálý přísun dostatečného množství nových veřejných klíčů...
Takže seznam použitých prvočísel samozřejmě existovat nesmí, protože by nebyl v bezpečí nikdo. Proto se ta prvočísla generují pořád dokola, tak je v bezpečí aspoň někdo, zatím. Ostatní mají smůlu, protože někdo ten seznam může už roky vytvářet a používat, není k tomu potřeba moc prostředků. A přiznejme si, kdo z nás by to nedělal, kdyby tu možnost měl? :o
-
Tak znovu: u RSA klíčů máme v případě RSA-2048 (dnes decentní volba, doporučení to už ale začínají tlačit k delším klíčům) na výběr řádově 2^1014 prvočísel. I kdybychom třeba 7/8 z různých důvodů (příliš krátká) vyřadili, máme jich pořád asi 2^1010.
Pro srovnání:
* Částic ve viditelné části vesmíru se odhaduje na 10^86 ≈ 2^286. Hodně štěstí s ukládáním všech známých prvočísel.
* AES má podle varianty 2^128 až 2^256 možných klíčů. Nepovažuje se za příliš praktické vygenerovat náhodný AES klíč a zkoušet, jestli nebude někde sedět. Ale asi by to bylo praktičtější než zmíněné kejkle s prvočísly na RSA.
* Pravděpodobnost, že na mě spadne meteor, si můžete dohledat za domácí úkol. Asi bude vyšší než crack AES-128. Tím nechci šířit poplašnou zprávu…
* Pravděpodobnost výhry v loterii taktéž. Tím ale nechci. Nabádat k žádnému sázení…
Pokud se někomu skutečně povede najít nějaké recyklované prvočíslo, bude to tedy nejspíš znamenat nějakou implementační chybu – například příliš zúžený okruh hledání prvočísel (např. ROCA*) nebo malá entropie (např. ~10 let stará kauza sdílených prvočísel u embedded zařízení).
*) V tomto případě došlo k oslabení kryptografie a možnému prolomení, ale nejsem si jist, jestli až tak, že by v praxi docházelo ke znovupoužití prvočísel. V principu ale takové zranitelnosti mohou k tomu vést.
-
2^1014 prvočísel
* Pravděpodobnost, že na mě spadne meteor, si můžete dohledat za domácí úkol.
Když vyřadíš všechna moc malá nebo moc velká N, a všechna N-1 dělitelná třemi, a tak dál...
Jak pravděpodobné je tohle: https://www.hradeckadrbna.cz/z-kraje/hradecko/1351-neznamy-predmet-prorazil-strechu-pergoly-a-udelal-diru-ve-fasade-mohlo-se-jednat-o-meteorit.html (https://www.hradeckadrbna.cz/z-kraje/hradecko/1351-neznamy-predmet-prorazil-strechu-pergoly-a-udelal-diru-ve-fasade-mohlo-se-jednat-o-meteorit.html)
Meteor možná ne, ale s bleskem bych to fakt neriskoval: http://xkcz.cz/795-podminene-riziko/ (http://xkcz.cz/795-podminene-riziko/)
Já vím že jich je i tak strašně moc, a že vyhrát první ve Sportce je téměř nemožné, ale kolik implementačních chyb v šifrovacích programech (o hardwaru nemluvě) se profláklo za posledních pět let? :'(
A pokud bys měl dostatek času, výkonu, a milion harddisků v Marylandu?
-
2^1014 prvočísel
* Pravděpodobnost, že na mě spadne meteor, si můžete dohledat za domácí úkol.
Když vyřadíš všechna moc malá nebo moc velká N, a všechna N-1 dělitelná třemi, a tak dál.
2048 bit sifrovanie pouziva najcastejsie 2x1024 bit prvocisla. Staci zlomit jedno, pocitajme s tym. 1024 bit cisel je 2^1023, lebo prvy bit je 1. Pocet prvocisel do cisla x sa vyjadri ako x/ln(x), teda tu 2^1023/ln(2^1023) < 2^1023/(2^9) = 2^1014. Vit to dal dobre hned.
Hledání vhodných prvočísel při výrobě klíčů je velmi náročné, zdaleka ne všechna se dají použít, tak jsou na to různé urychlující zkratky.
Casovo najnarocnejsie je ziskat dost entropie. Inak sa pouziva pravdepodobnostny test prvociselnosti ako napriklad Rabin-Miller. Vdaka tomu netreba mat ulozene a ani vediet vsetky prvocisla.
A pokud bys měl dostatek času, výkonu, a milion harddisků v Marylandu?
https://xkcd.com/538/
Mam velmi vela vykonu, ale dlhe RSA som este nezlomil.
-
Budu-li mít k dispozici milion disků o 20 TiB, uložím tam něco přes 2^37 prvočísel o délce 1024 bitů, pokud budu počítat, že první a poslední číslice ve dvoujové soustavě je jednička, a tedy by mi stačilo 1022 bitů na prvočíslo. Spočítáno jako log[2](8*20*1024^4/1022). To je dost málo. Mám trochu tušení, že tolik prvočísel bych s dobrou entropií na svém starém počítači prošel v řádu dní, a nepotřebuju úložný prostor. Aspoň tak nějak mi to na starém notebooku vycházelo v Javě přes něco jako BigInteger.probablyPrime se SecureRandom nebo tak něčím, bez speciálních optimalizací.
Ano, nějaká malá prvočísla vyřadíme, myslím, že těch 7/8 je dostatečně pesimistických. O čísel kongruentních s 1 (mod 3) nevím – pokud takováto pravidla znáte, sem s nimi, mohu je započítat. Samotné toto pravidlo by vyřadilo hádám polovinu prvočísel (pokud kongruence s (mod 3) je mezi prvočísly rovnoměrně rozložena mezi 1 a 2). Nemyslím si, že bychom se dostali pod 2^1000 použitelných prvočísel, což je pořád dost.
Pozná…ka o enyropii je dobrá. A hlavně je to další argument, proč spoléhat se na pomalé procházení prvočísel ke rozbité již dnes – útočník při procházení všech možností nepotřebuje generovat dost entropie.
Terminilogický detail: i čísla začínající nulou mohu řadit do 1024-bitových, proto 2^1024. Druhá věc je, že tato čísla nejspíš vyřadím jako příliš malá…
-
Ale ty nemusíš ukládat všechna prvočísla, stačí jen ta už získaná a zatím nerozlomené klíče. A pořád sbírat a sbírat, času máš dost.
-
Budu-li mít k dispozici milion disků o 20 TiB, uložím tam něco přes 2^37 prvočísel o délce 1024 bitů, pokud budu počítat, že první a poslední číslice ve dvoujové soustavě je jednička, a tedy by mi stačilo 1022 bitů na prvočíslo. Spočítáno jako log[2](8*20*1024^4/1022). To je dost málo.
Nie ze by to menilo vela, ale:
To ide ulozit aj efektivnejsie, lebo tie cisla nie su nahodne. Co tak si ukladat len rozdiel k dalsiemu prvocislu? Alebo sa na to pozrieme a povieme si, ze vsetky zaujimave prvocisla sa daju napisat ako
6k+1
6k+5
cim zapiseme iba 1/3 cisel do bitmapy. Pri rozsireni na nasobky 30+x sme na 26% dlzky. A tak dalej s nasobkami 210, 2310, 30030 a da sa to neobmedzene rozsirovat a platit predpocitanim za ulozisko.
-
co tak se smirit s tim, ze na to nikdo z vas nema ?
-
Co jsou ta „ta už získaná“ prvočísla?
Ad času máme dost – OK, zkuste tedy nějak zhruna vyčíslit, kolik času budete potřebovat. Můžete třeba vzít stonásobek výkonu BTC sítě (to je výkon, jaký člověk jen tak nezíská) a spočítat, jestli se toho vůbec dožijete.
Jinak jestli jde o útoky na chybně implementované generování klíčů – tam to smysl mít může. Ale tam asi nebudete potřebovat vědět nic detailnějšího o struktuře prvočísel…
K tomu počtu prvočísel na milionu HDD: Zdálo se mi to nějak málo, tak jsem to překontroloval, a zapomněl jsem to vynásobit tím milionem, výsledek je tedy pro jeden disk. I tak je to „jen“ něco přes 2^57. Pokud bychom zvali návrh od aaa, dostali bychom se tak na 2^60 prvočísel.
V neposlední řadě: I kdybychom čistě teoreticky zvládli uložit všechna potenciálně relevantní prvočísla (takže bychom do jedné elementární částice jich asi museli uložit několik), co s tím dál? Projít to jedno po druhém a všechna vyzkoušet? Good luck, výsledku se nedožijete. (To není výhružka, jen konstatování časové náročnosti.) Ani teď nevím, jestli procházení prvočísel bude efektivnější čtením z HDD, nebo generováním dalších a dalších prvočísel on the fly.
Přínosy seznamu prvočísel jsou totiž hrozně diskutabilní. Šlo by snadno zjistit, kolikáté prvočíslo v seznamu je N (a naopak, kolik je n-té prvočíslo v seznamu je), otázka ovšem je, k čemu by to bylo prakticky. A jinak přínos pro kryptoanalýzu RSA moc nevidím.
-
co tak se smirit s tim, ze na to nikdo z vas nema ?
Tak zatímco o Riemannově hypotéze se říká, že na provedení důkazu možná ještě ani neexistuje příslušný matematický aparát, nebyl vynalezen, tak např. o problému P vs. NP se naopak povídá, že by ho mohl dokázat i ne-matematik. Ale za obojí jsou stejné peníze ;-)
Tam věřím, že nějaký programátor tady by to možná zvládnul, ale na Rootu budete za exota v obou případech, i když se o to budete jenom pokoušet...
-
Přínosy seznamu prvočísel jsou totiž hrozně diskutabilní. Šlo by snadno zjistit, kolikáté prvočíslo v seznamu je N (a naopak, kolik je n-té prvočíslo v seznamu je), otázka ovšem je, k čemu by to bylo prakticky. A jinak přínos pro kryptoanalýzu RSA moc nevidím.
Tak jestli je počet prvočísel n/ln(n) tak pro 2048 bitů je to zefektivnění cca 1500x (za předpokladu okamžité čtení z disku, nulové další výpočty..) proti naivnímu bruteforce.
Když přidám různá CPU-skorozadarmo síta že nám to zefektivní cca 100x, tak máme vylepšení cca 15x, což žádnou dnes považovanou za bezpečnou šifru nemůže ani vzdáleně ohrozit.