zkouska 10.2.2006

[darkness]

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.

[tutchek]

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.

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)

ukazte, ze staci tridici sit hloubky S(k) + 2M(k)

[darkness]

dekuji, opraveno btw a mam to

[wintermute]

Takovýhle tvrďárny tu máte, jo? To já si dneska dal u Kučery Aho-Corasicka a v pohodě.

[tutchek]

Takovýhle tvrďárny tu máte, jo? To já si dneska dal u Kučery Aho-Corasicka a v pohodě.

ne, nemame tu takovy tvrdarny, to neni zkouska.. to je jen pripousteci test ke zkousce

[Návštěvník]

Mám to Chachá...!!! Nevím, jak Tuchek, ale já spal ten den minimálně a na ústním jsem byl totálně vymaštěnej. Kdybych neměl plnej počet bodů, tak snad vyletím. Ale já to mám Btw. jistá slečna řekněme Káá je zářný příklad toho, že jde dostat jedničku za 1.5 bodu.

[random]

Teda já se zapomněl přihlásit a navíc zkomolil Tutchkovi jméno, za což se hluboce omlouvám jeho papučím.

[qk_]

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]

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

mno, ja som to pocital takto:

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

[Návštěvník]

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

mno, ja som to pocital takto:

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

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

[nytram]

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

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

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