Hlavní stránka Fóra Forum pro soutěžící SOČ 42. celostátní přehlídka ONLINE 42. CP SOČ online – obor 01 matematika a statistika Odpověď na téma: 42. CP SOČ online – obor 01 matematika a statistika

#24392
Václav Zvoníček
Host

1) Pokud si definujeme náhodnou veličinu jako četnost jednotlivých členů posloupnosti, pak aby pseudonáhodná posloupnost byla náhodná, musí být rozdělení této náhodné veličiny rovnoměrné. Větu, kterou jste zmínili, jsem takto v práci vyslovil, aby byl vidět účel pseudonáhodné posloupnosti, ačkoliv to plyne i z názvu.

2) V průběhu práce jsem Möbivu funkci použil při důkazu, že pro posloupnosti nad tělesem pro p různé od 3 neobdržím stejnou četnost prvků. Dále jsem však nepřemýšlel příliš o tom, jak Möbivu funkci opět vrátit do hry, ale spíše se zabýval otázkou, jak bych mohl pomocí stopy generovat posloupnost jinak. Konkrétně mám na mysli to, že v při uvedeném generování bereme stopu postupně prvků x, x^2, x^3, … a mě právě zajímá, jak by se posloupnost změnila, když by exponenty primitivního prvku x byly povel jinak, třeba pomocí hashovací funkce nebo kvadratického kongruentního generátoru.

3) Ano, je to tak. Vypadá to, že když se soustředím na četnost jednotlivých prvků, pak nedostanu nikdy rovnoměrné rozdělení. Pro p = 3 jsem se tomu přiblížil, ale, jak říkáte, od poloviny je vlastně totožná, takže mohu hovořit maximálně jen o první polovině. To mě nicméně vedlo k tomu, na co se přesně ptáte. Jakmile jsem došel k tvrzení o stejné polovině pro p = 3, napadlo mě, jestli by tato posloupnost nešla využít jako nějaký ověřovací klíč:
Osoba A komunikuje s osobou B a využívá nějakého klíče. Osoba A má první polovinu posloupnosti pro p = 3 a chce si ověřit, že B je důvěryhodná osoba. Nemůže však poslat druhou polovinu, takže aby si to ověřil, musí vidět, že osoba B dokáže vygenerovat stejnou posloupnost, ale různou na znaménko.
Toto je jen stručný demonstrační nápad, k samotné realizaci a konkrétním implementacím jsem se nedostal. Byl by však spíše jen takovou ukázkou.

4) To mě právě překvapilo. Až zpětně jsem si všiml, že dokazovali stejné tvrzení o stopě, tedy že pošle p^{n-1} prvků na prvek p, ale dále se tomu nevěnovali. V článku jsem se tedy opravdu dočetl jen o tom, že posuzovali posloupnost na základě periody, autokorelace a korelace, nikoliv četnosti.

5) Při začátku této SOČ jsem se díval na nějaké takové testy, ale nakonec jsem se rozhodl, že do toho nebudu takto zabíhat a využil jsem jen jednoduché metody. I díky nim jsem došel k, podle mě, zajímavým výsledkům. Tedy vím, že nějaké existují, ale neznám konkrétní.