Hric - Příklad na zápočet - potřebuju poradit...

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Ellrohir »

povinnosti k zápočtu z algoritmů u Hrice si plním výpočtem 9 z jeho příkladů a jeden z nich zní :

"Předpokládejte že v RSA se prvočísla p a q liší od odmocniny z n (jejich součinu) nanejvýš o jeden bit, tedy jsou téměř stejně velká. Kolik rozkladů hrubou silou musím vyzkoušet?"

já to buď nechápu a nebo je odpověď skutečně to, že stačí jeden - odmocninu z n znám a když si určím nejbližší vyšší, resp. nebližnší nižší prvočíslo, tak to musí ten správný rozklad...

ale přijde mi, že je to nějaký moc jednoduchý, takže asi něco přehlížím/nechápu zadání... :(
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Tuetschek »

No do vzdalenosti +- 1 bit se ale tech prvocisel urcite vejde vic, ne? A nejde i o to testovani prvocisel?
Plug 'n' Pray.
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Osiris »

Ellrohir píše:...
Nebylo by nejjednoduší udělat si dva cykly od 1 do log_2(sqrt(n)) a zkouset prehazovat 1 bit pro jedno cislo (1 cyklus) a druhy bit pro druhe cislo (2. cyklus) a pak to pronasobit a testovat to? Slozitost je log_2(n)^2 * (nasobeni cisel + test prvociselnosti)
Osiris
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Ellrohir »

2Tuetschek : řekl bych, že o to nejde - určování prvočíselnosti je snad u RSA až sekundární problém, ne? (resp. dá se snad předpokládat, že když už někdo bude chtít zkošuet brutal attack, tak bude schopen určit efektivně prvočíselnost zkoušených možností)...spíš to bude v tom, jak říkáš, že do +/- 1 bit se jich vejde víc než právě dvě...teď ale jak teda určit závislost mezi hodnotou odmocniny z n a počtu prvočísel lišících se o +/- jeden bit, což bude zjevně odpověď na tuto otázku? já sem asi po čtyřech hodinách s algoritmy úplně blbej :roll:

2Osiris : asi trochu nechápu :oops: nicméně určitě vím, že mě je jedno, co by bylo jednodušší...já mám zodpovědět otázku, kolik je potřeba zkusit možností při brute force (ale když člověk ví, že rozdíl prvočísel je max 1 bit od odmocniny ze součinu)
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Osiris »

Ellrohir píše:...
Těch prvočísel bude fakt hodně, protože tenhle tvůj problém je ekvivalentní s tím, najít všechna prvočísla od sqrt(n)/2 do 2*sqrt(n) (nebo nějaká takováhle konstanta), což je pravděpodobně ekvivalentní vyřešit faktorizaci obecného n.

Jinak ten můj algoritmus potřebuje vygenerovat log_2(n) čísel, což už je rozumné. Třeba pro n dlouhé 2048 bitů bude potřebovat zkusit cca 2048 čísel.
Osiris
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Ellrohir »

to je hezký a díky za to, jenomže jak znovu říkám - nejde o to, upravit metodu tak, aby fungovala co nejefektivněji...jde o to analyzovat a říct, jak bude fungovat ta neefektivní :wink:

pakliže je pravda to, co předpokládáš - že to je ekvivalentní faktorizaci obecného n - pak je to, co jsem chtěl slyšet :)
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Osiris »

Ellrohir píše:to je hezký a díky za to, jenomže jak znovu říkám - nejde o to, upravit metodu tak, aby fungovala co nejefektivněji...jde o to analyzovat a říct, jak bude fungovat ta neefektivní :wink:

pakliže je pravda to, co předpokládáš - že to je ekvivalentní faktorizaci obecného n - pak je to, co jsem chtěl slyšet :)
Pod větou Kolik rozkladů hrubou silou musím vyzkoušet bych si představil, kolik MINIMÁLNĚ. To taky můžeš říct, že hledání Hamiltonovské kružnice na kružnicích je O(n!), i když je to triviální.
Osiris
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Ellrohir »

no nevim nevím...mě prostě přijde, že v tomhle případě opravdu není účelem vylepšit "hackovací algoritmus" a že "hrubou silou" se opravdu myslí "hloupé" zkoušení všech možných prvočísel...to je jako, kdyby byla otázka na hashování a na počet nutně vyzkoušitelných možností při "slovníkovém útoku" - a já místo hledání závislosti počtu možností na délce slova a výběru znaků začal chytračit, jak útočníka vylepšit, aby jich nemusel projít tolik...to by podlě me stála otázka "navrhněte lepší heuristiku pro útok na RSA šifru", kdybych chtěl, abych vylepšoval základní "hloupý" algoritmus...

a klidně si to napíšu do zdůvodnění řešení, že jsem to zadání prostě pochopil takhle...můj problém ale je, že se mi nedaří tu závislost počtu možností na n (potažmo odmocnině z n) najít :(
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Osiris »

Ellrohir píše:no nevim nevím...mě prostě přijde, že v tomhle případě opravdu není účelem vylepšit "hackovací algoritmus" a že "hrubou silou" se opravdu myslí "hloupé" zkoušení všech možných prvočísel...to je jako, kdyby byla otázka na hashování a na počet nutně vyzkoušitelných možností při "slovníkovém útoku" - a já místo hledání závislosti počtu možností na délce slova a výběru znaků začal chytračit, jak útočníka vylepšit, aby jich nemusel projít tolik...to by podlě me stála otázka "navrhněte lepší heuristiku pro útok na RSA šifru", kdybych chtěl, abych vylepšoval základní "hloupý" algoritmus...

a klidně si to napíšu do zdůvodnění řešení, že jsem to zadání prostě pochopil takhle...můj problém ale je, že se mi nedaří tu závislost počtu možností na n (potažmo odmocnině z n) najít :(
Jenže ten příměr je špatný. Tady je to zadání osekané. To je, jako kdybych ti dal prolomit hash slovníkovým útokem s tím, že bych ti řekl, že se jedná o měsíce a dny v týdnu (celkem 19 možností). Šel bys na to tak, že bys zkoušel všechny možné kombinace písmen a slov? Asi ne. Hrubou silou zde znamená prostě vyzkoušet všech 19 možností.

Btw. víš, co je to vůbec heuristika? Tohle není heuristika, to co jsem napsal. Ten můj algoritmus je korektní a DETERMINISTICKÝ a vždy najde rozklad n na zmíněná p a q hodně rychle - samozřejmě za té zmíněné podmínky o 1 bitu.
Osiris
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Tuetschek »

Osiris: myslim, ze mas pravdu, s tim konceptem ... ze Hricovi fakt jde o to, kolik MUSIM vyzkouset, tj. minimalni pocet ... protoze jinak bych si mohl vymyslet libovolne hodne velke cislo a nejaky algoritmus by se uz vzdycky nasel :lol: ... ale ten tvuj algoritmus jsem z toho taky nepobral. Co je "prehazovat bit"?
Plug 'n' Pray.
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Osiris »

Tuetschek píše:Osiris: myslim, ze mas pravdu, s tim konceptem ... ze Hricovi fakt jde o to, kolik MUSIM vyzkouset, tj. minimalni pocet ... protoze jinak bych si mohl vymyslet libovolne hodne velke cislo a nejaky algoritmus by se uz vzdycky nasel :lol: ... ale ten tvuj algoritmus jsem z toho taky nepobral. Co je "prehazovat bit"?
Díky. No, myslím to úplně jednoduše takhle: vezmeš si binární zápis odmocniny z n. Dále uděláš množinu A = {x | x se liší v maximálně jednom bitě}. Tu zkonstruuji tak, že si vezmu ten binární zápis odmocniny z n a postupně zneguju každý bit toho binárního zápisu a zařazuji to do A. Je jisté, že p,q leží v A. Velikost A je log_2(sqrt(n)) + 1. Udělám si kartézský součin A x A, a pro každé (a,b) v A x A otestuji, zda a*b = n. Pak p = a a q = b.
Osiris
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Tuetschek »

Osiris píše:Díky. No, myslím to úplně jednoduše takhle: vezmeš si binární zápis odmocniny z n. Dále uděláš množinu A = {x | x se liší v maximálně jednom bitě}. Tu zkonstruuji tak, že si vezmu ten binární zápis odmocniny z n a postupně zneguju každý bit toho binárního zápisu a zařazuji to do A. Je jisté, že p,q leží v A. Velikost A je log_2(sqrt(n)) + 1. Udělám si kartézský součin A x A, a pro každé (a,b) v A x A otestuji, zda a*b = n. Pak p = a a q = b.
Aha ... ja jsem to ale pochopil tak, ze p a q se lisi od sqrt(n) max. o 1 bit svou delkou ... tohle si myslim, ze neco takoveho nema moc sanci nastat :roll: .
Plug 'n' Pray.
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Osiris »

Tuetschek píše:
Osiris píše:Díky. No, myslím to úplně jednoduše takhle: vezmeš si binární zápis odmocniny z n. Dále uděláš množinu A = {x | x se liší v maximálně jednom bitě}. Tu zkonstruuji tak, že si vezmu ten binární zápis odmocniny z n a postupně zneguju každý bit toho binárního zápisu a zařazuji to do A. Je jisté, že p,q leží v A. Velikost A je log_2(sqrt(n)) + 1. Udělám si kartézský součin A x A, a pro každé (a,b) v A x A otestuji, zda a*b = n. Pak p = a a q = b.
Aha ... ja jsem to ale pochopil tak, ze p a q se lisi od sqrt(n) max. o 1 bit svou delkou ... tohle si myslim, ze neco takoveho nema moc sanci nastat :roll: .
No to je sporné, dá se to pochopit oběma způsoby. Když mě někdo řekne, že číslo a se liší od čísla b nanejvýš o 1 bit, rozhodně bych si to představil tak, že stačí někde znegovat bit a z čísla a dostanu b. Tohle je akademický příklad, takže se asi moc nehledí jestli to reálně může nastat.
Osiris
banejee

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od banejee »

riesim teraz tuto istu ulohu.. riesenie mi dost pomohlo.. ale keby sa jednalo o to ze sa meni postupne kazdy bit, tak by tam bolo podla mna.. p a q sa lisia od sqrt(n) najviac "v" jednom bite.. :wink:
banejee

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od banejee »

mohol by mi niekto pomoct s 2 ulohami? nie som si isty co tam napisat.. uz len tieto mi chybaju a dost by mi to pomohlo :)

Popište (pseudopolynomiální) algoritmus pro rešení souctu podmnožiny
Vysvetlete, proc tyto algoritmy nelze považovat za polynomiální.

Heuristika najbližšieho bodu
Na zaciatku vytvoríme cyklus z jednoho lub. bodu.
V jednotlivých krokoch postupne hladáme vrchol u, ktorý
nie je v cykle a je najbližšie k cyklu, k nejakému vrcholu
v. Rozšírime cyklus pridaním u za v a opakujeme, kým
v cykle nie sú všetky vrcholy. Ukážte, že táto heuristika
vracia cyklus, ktorý je najviac dvaktát dlhší než optimálna
cesta (pri platnosti trojuholnikovej nerovnosti).
Navrhnite zlepšenie k popísanej heuristike.
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“