Riemannova hypoteza

[eee?]

co tak se smirit s tim, ze na to nikdo z vas nema ?

[Reklama]

[Vít Šesták (v6ak)]

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.

[Honza]

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...

[jouda]

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.