->KaNeiet
Laikam būsi nepareizi mani sapratis. Mēģināšu skaidrot vēlreiz.
1) 2^52 ir problēmas SHA-1 “smagums”.
2) 52-bit subset sum problēmas “smagums” arī ir 2^52.
3) To 52-bit Subset sum problēmu var atrisināt laikā, kas proporcionāls 2^26.
4) Tā kā NP problēmas var pārveidot vienu otrā, tad IESPĒJAMS, ka arī SHA-1 problēmu var atrisināt laikā, kas proporcionāls 2^26. Man nav pieejams šāds algoritms (bet pieļauju, ka kādam ir). Lai NP problēmas pārveidotu no vienas uz otru arī ir jāpasvīst.
5) Kas attiecas uz dinamisko programmēšanu (DP), tad ar to šādas problēmas vispār risinās polinomālā laikā. Nelaime tikai tāda, ka ne visu var paņemt ar to DP. Tāpēc arī minēju par problēmas blīvumu. Savulaik tika izmantota viena kriptogrāfijas metode, kas bija bāzēta uz zema blīvuma subset-sum, bet ar DP to lauza zibenīgi, pofig 64, 128 vai 256 biti.
Nu un visbeidzot par 2^52 atrisināšanu nedēļas laikā uz mājas kompja.
– Nedēļā ir 7 dienas, katrā pa 24 stundām, katrā pa 60 minūtēm, katrā pa 60 sekundēm. Tātad nedēļā ir 604800 sekundes.
– 2^52 / 604800 = 7446427955, jeb aptuveni 7G operācijas.
– Moderni kompju taksts frekvence ir virs 3GHz, 4 kodoli dod 12GHz (jo šos uzdevumus var viegli palaist paralēlās plūsmās).
– 7G operācijas pret 12GHz ir samērojami lielumi.
– Modernam mājas kompim ir arī videokarte, kurā var ielādēt uzdevumu. (Reizēm tās videokartes rēķina ātrāk kā CPU.)
Manuprāt ar šiem aprēķiniem pietiek, lai saprastu, ka 2^52 var sarēķināt nedēļas laikā uz mājas kompja ar brute force.
Reāli, tā ir tukša diršana, ko tu mums te stāsti. Tur, kur cilvēkiem par šito arī maksā, nevis paši paņem, ir jau chipi iekšā ar vajadzīgajām instrukcijām, atlauž minūtēs.
Vispār komēdijas jau labās šeit ir, vajadzētu izveidot sadaļu “Nedēļas pērle”, un tad katru mēnesi izvēlēties labāko ar balsošanu un dot balvas. Gada balva varētu arī būt kas nopietns, piemēram diskusija par problemātisko tematu ar d_l.
