zkouska 10.2.2006
- darkness
- Matfyz(ák|ačka) level II
- Příspěvky: 70
- Registrován: 15. 1. 2005 13:24
- Typ studia: Informatika Mgr.
- Bydliště: pod mostem (Nuselskym)
- Kontaktovat uživatele:
zkouska 10.2.2006
takze zadani: Zadny aho-corasick
(opraveno)
1) posloupnost je k-setridena (kazdy prvek je nejdale k pozic od sveho rektniho umisteni), mame tridici sit sirky k s hloubkou S(k) a merge sit se sirkou 2k a hloubkou M(k)
ukazte, ze staci tridici sit hloubky S(k) + 2M(k)
2) RSA - zadana dve prvocisla p, q a dve cisla e1 a e2.
Ukolem bylo spocitat soukromy klic, kazdy krok okomentovat a popr. rict, proc to nejde.
(konkretni hodnoty p=17, q=13, e1=5, e2=3)
takze pro e2 to nelze, pze cislo 16*12 je delitelne 3.
3) Asi klasicky - prevod NP problemku
Melo se dokazat, ze PSP je NP-uplny problem
Petkovy soucet podmnoziny (PSP) je zvlastni pripad SP (soucet podmnoziny), lisi se tim, ze vsechna cisla a1,...,an,b jsou delitelna 5, ale princip je stale stejny - vybrat podmnozinu z prvku a1,...,an tak, aby soucet byl b.
(opraveno)
1) posloupnost je k-setridena (kazdy prvek je nejdale k pozic od sveho rektniho umisteni), mame tridici sit sirky k s hloubkou S(k) a merge sit se sirkou 2k a hloubkou M(k)
ukazte, ze staci tridici sit hloubky S(k) + 2M(k)
2) RSA - zadana dve prvocisla p, q a dve cisla e1 a e2.
Ukolem bylo spocitat soukromy klic, kazdy krok okomentovat a popr. rict, proc to nejde.
(konkretni hodnoty p=17, q=13, e1=5, e2=3)
takze pro e2 to nelze, pze cislo 16*12 je delitelne 3.
3) Asi klasicky - prevod NP problemku
Melo se dokazat, ze PSP je NP-uplny problem
Petkovy soucet podmnoziny (PSP) je zvlastni pripad SP (soucet podmnoziny), lisi se tim, ze vsechna cisla a1,...,an,b jsou delitelna 5, ale princip je stale stejny - vybrat podmnozinu z prvku a1,...,an tak, aby soucet byl b.
Naposledy upravil(a) darkness dne 10. 2. 2006 16:38, celkem upraveno 1 x.
- tutchek
- Site Admin
- Příspěvky: 795
- Registrován: 21. 9. 2004 00:40
- Typ studia: Informatika Mgr.
- Login do SIS: tulam4am
- Bydliště: Praha, Bohnice
- Kontaktovat uživatele:
Re: zkouska 10.2.2006
ad1) posloupnost je k-setridena (kazdy prvek je nejdale k pozic od sveho rektniho umisteni), mame tridici sit sirky k s hloubkou S(k) a merge sit se sirkou 2k a hloubkou M(k)darkness píše:takze zadani: Zadny aho-corasick
1) dokazat neco u tridici site, nepamatuji si to presne, ale byl tam nejaky predpoklad, ze prvek je vzdalen max k pozic od sveho spravne pozice v setridene posloupnosti. (k je sirka tridici site, 2k je sirka slucovaci site)
a melo se dokazat, ze to lze setridit pomoci S(k) + 2 M(k)
(radsi me opravte)
2) RSA - zadana dve prvocisla p, q a dve cisla e1 a e2.
Ukolem bylo spocitat soukromy klic, kazdy krok okomentovat a popr. rict, proc to nejde.
(konkretni hodnoty p=17, q=13, e1=5, e2=3)
takze pro e2 to nelze, pze cislo 16*12 je delitelne 3.
3) Asi klasicky - prevod NP problemku
Melo se dokazat, ze PSP je NP-uplny problem
Petkovy soucet podmnoziny (PSP) je zvlastni pripad SP (soucet podmnoziny), lisi se tim, ze vsechna cisla a1,...,an,b jsou delitelna 5, ale princip je stale stejny - vybrat podmnozinu z prvku a1,...,an tak, aby soucet byl b.
ukazte, ze staci tridici sit hloubky S(k) + 2M(k)
exAdmin. Magistr přes umělou inteligenci. Právník přes daně.
- wintermute
- Matfyz(ák|ačka) level III
- Příspěvky: 153
- Registrován: 23. 5. 2005 22:06
- Typ studia: Informatika Mgr.
Mel bych dotaz k tomu RSA. Zkousel sem si to doma spocitat a mam problem u toho multiplikativniho inversu. Podle poznamek ma vyjit ax+ny, takovy ze ny je identicky s nulou a z ax to dostanu...no problem je ze mne vyslo ny -95 a ax 96, takze NSD je sice 1, ale nejak to nedpovida tomu co je v poznamkach. Muzete sem nekdo hodit ten vypocet inversu (mne to vyslo PuK(5,221) A PrK(2,221) )
- nytram
- Matfyz(ák|ačka) level II
- Příspěvky: 68
- Registrován: 4. 1. 2005 15:54
- Typ studia: Informatika Bc.
- Bydliště: da B-9'th floor
- Kontaktovat uživatele:
mno, ja som to pocital takto:qk_ píše:Mel bych dotaz k tomu RSA. Zkousel sem si to doma spocitat a mam problem u toho multiplikativniho inversu. Podle poznamek ma vyjit ax+ny, takovy ze ny je identicky s nulou a z ax to dostanu...no problem je ze mne vyslo ny -95 a ax 96, takze NSD je sice 1, ale nejak to nedpovida tomu co je v poznamkach. Muzete sem nekdo hodit ten vypocet inversu (mne to vyslo PuK(5,221) A PrK(2,221) )
e=5;
(p-1).(q-1) = 192;
5*d = 1 + k.(p-1).(q-1)
a vieme, ze 0 < d < 192
teda max. 5*d = 5*192 = 960
a potom korigujem "k" tak, aby sa to rovnalo
Quod Erat Demonstrandum.
hu, takze podle tohohle je 2 dobre...192*2+1 = 385...tedy d je 77...hmmm, tak tomu opravdu nerozumim, jak k tomu dojit logicky a ne metodou pokus omylnytram píše:mno, ja som to pocital takto:qk_ píše:Mel bych dotaz k tomu RSA. Zkousel sem si to doma spocitat a mam problem u toho multiplikativniho inversu. Podle poznamek ma vyjit ax+ny, takovy ze ny je identicky s nulou a z ax to dostanu...no problem je ze mne vyslo ny -95 a ax 96, takze NSD je sice 1, ale nejak to nedpovida tomu co je v poznamkach. Muzete sem nekdo hodit ten vypocet inversu (mne to vyslo PuK(5,221) A PrK(2,221) )
e=5;
(p-1).(q-1) = 192;
5*d = 1 + k.(p-1).(q-1)
a vieme, ze 0 < d < 192
teda max. 5*d = 5*192 = 960
a potom korigujem "k" tak, aby sa to rovnalo
- nytram
- Matfyz(ák|ačka) level II
- Příspěvky: 68
- Registrován: 4. 1. 2005 15:54
- Typ studia: Informatika Bc.
- Bydliště: da B-9'th floor
- Kontaktovat uživatele:
no, metoda pokus/omyl je vhodna len pre male cisla, resp. na pisomke nebolo povedane, aby som pouzil algoritmus z prednasky, konkretne EXTENDED_EUCLID. Teda som si to takto "zjednodusil".Anonymous píše: hu, takze podle tohohle je 2 dobre...192*2+1 = 385...tedy d je 77...hmmm, tak tomu opravdu nerozumim, jak k tomu dojit logicky a ne metodou pokus omyl
Algo. E_EUCLID(a,b,d,x,y) { vopred sa ospravedlnujem za prologovsky zapis } ti vrati d = NSD(a,b) a "x" a "y" su koeficienty pre "d", kedze "d" mozeme zapisat ako d = ax + by.
Z toho plynie: ax = d - by, kde pre pre potreby RSA je "a" = "e", "d" = 1,
"b" = (p-1)*(q-1), "y" = "k", a "x" je ten multiplikativny inverz...aspon tak som to pochopil....snad to dava zmysel....
Quod Erat Demonstrandum.