streda 5. marca 2014

Empirický test (v matike)

Sú toto skutočne náhodné čísla?
Je bežne považovaný na zbytočný nežiadúci. Asi ho však budem v budúcnosti odporúčať. Jeden z mojich študentov, Morema, robí ročníkovú prácu o využití náhodných a pseudonáhodných čísel v kryptografii. Jedna z najjednoduchších metód na generovanie pseudonáhodných čísel je lineárny kongruenčný generátor. Znie to desivo, ale v princípe je to jednoduché. Majme prirodzené číslo x0 s hodnotu, ktorou generátor nainicializujeme (angl. seed). Vymyslime si ďalšie prirodzené čísla a, c, m. Ďalšie náhodné číslo získame predpisom:  
x1 = (a x0 + c) mod m,
kde mod označuje zvyšok po delení. Samozrejme x1 potom využijem ako ďalší seed a takto si náhodných čísel nagenerujem celú fúru. Lenže asi sa mi stane, že sa mi nejaké časom objaví zasa (zopakuje), čo automaticky značí, že sa mi zopakuje aj to nasledujúce po ňom v minulosti. Do dôsledku to znamená, že sa mi ich zopakuje vcelku dosť a v známom poradí. Pre jednoduchosť, nech x4 = x1, takže x5 = x2, x6 = x3, x7= x4 = x1 a vidím, že čísla od x1 do x3 sa už budú opakovať stále. Ak viem toto vypozorovať, tak už pre mňa generátor nie je náhodný. Takže toto je spôsob ako takýto náhodný generátor prekuknúť, za predpokladu, že sa ho vieme pýtať dostatočne často. (Predpoklad "asi sa mi zopakuje" je pravdivý, ak budem generovať aspoň m+1 čísel, keďže zvyšok po delení m mi dá najviac m rôznych hodnôt.)

Potiaľto teória. Morema chcel otestovať, že dĺžka neopakujúcej sa podpostupnosti náhodných čísel bude závisieť od m. Keďže má pravého informatického ducha, napísal kus kódu v pytónovi a spustil ho s hodnotami m = 10,  c = 11, a = 20, x0 = 0. "Výsledek byl poněkud rozpačitý": 0, 1, 1, 1, 1, ...  Až tak škandálne to nie je: keďže 11 mod 10 = 1 a zároveň  (20 . 1 + 11) mod 10 = 1. Ľaľa, problém.

Kde je pes zakopaný? Najskôr asi bude v kóde, ale to sme rýchlo vylúčili. Ja som nikdy poriadnu algebru neabsolvoval, ale z populárnej literatúry som mal spomienky, že "veci mod n" sa správajú slušnejšie, ak je n prvočíslo. Ďalším krokom je samozrejme wikipedia. A vynorili sa nové poznatky užitočné pre Moremovu prácu. 
Ponaučením nemá byť, čítaj literatúru poriadne (čo najporiadnejšie). To v skutočnosti nejde, niečo sa vždy dá prehliadnuť. Ale odskúšaj, pokiaľ to ide, nech vidíš, či tomu rozumieš dobre, resp. či to funguje správne.


Žiadne komentáre:

Zverejnenie komentára