Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

6. Feladatok

6. Feladatok

1. Miért nem perfekt titokmegosztás az ( 5 , 5 ) küszöbrendszerre a következő konstrukció?

A titok egy 10-jegyű szám, amelynek első két számjegyét megkapja az első résztvevő, a második kettőt a második és így tovább.

2. Vizsgáljuk meg, hogy mennyire (nem) hatékonyak a Benaloh–Leichter-, illetve az Ito–Saito–Nishizeki-konstrukciók a ( t , n ) -küszöbrendszerekhez, s hasonlítsuk össze őket!

3. Adjunk meg „gyors” algoritmust adott ? 0 -ból a megfelelő ? 0 felírására!

4. Az utolsó fejezet összefoglaló táblázatában lévő hozzáférési rendszerek mindegyikénél (a küszöbrendszerek kivételével) döntsük el, hogy a Benaloh–Leichter-, illetve az Ito–Saito–Nishizeki-konstrukció ad-e hatékonyabb titokmegosztást!

5. Keressünk ideális Martin–Jackson–O’Keefe-konstrukciót az összefoglaló táblázat 11., 14. és 16. sorában álló hozzáférési rendszerekhez!

6. Igazoljuk, hogy a Martin–Jackson–O’Keefe-konstrukció perfekt titokmegosztást ad meg!