Generátor náhodných čísel

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Generátor náhodných čísel je výpočetní nebo fyzické zařízení, které generuje řadu náhodných čísel, tj. čísel která postrádá jakýkoliv vzor (sekvenci, předvídatelnost).

Praktické využití a aplikace[editovat | editovat zdroj]

Náhodná čísla mají uplatnění v různých oborech, kde je kladen důraz na proměnlivost systému. Největší využití mají zejména v oborech jako šifrování, počítačové simulace a modelování nebo v hazardních hrách. V některých situacích, jako jsou bezpečnostní systémy, jsou upřednostňovány fyzikální/hardwarové metody generování oproti metodám softwarových vytvářející pseudonáhodná čísla.

Pravá náhodná vs. pseudonáhodná čísla[editovat | editovat zdroj]

Principiálně existují dva způsoby, jak generovat náhodná čísla. Prvním způsobem je generování tzv. pseudonáhodných čísel (PRNG), kdy je použit algoritmus, který generuje zdánlivě náhodná čísla. Druhým způsobem generování náhodných čísel je Pravý generátor náhodných čísel (TRNG), který využívá náhodnost získanou z fyzikálních jevů. Rozpoznání pravých a pseudonáhodných čísel může být velmi problematické. K ověřování důvěryhodnosti algoritmů jsou používány statistické analýzy.

Metody generování[editovat | editovat zdroj]

Fyzikální/hardwarové metody[editovat | editovat zdroj]

Lávová lampa.

Prvním způsobem generování náhodných čísel bylo vrhání kostkami, házení mincí, ruleta. Jde o metody, které jsou používány dodnes zejména v hazardních hrách. Pro použití v kryptografii nebo statistice jsou ale příliš pomalé a neúčinné.

Fyzikální generátor náhodných čísel může být založen na velkém množství principů, jedním z nich může být nepředvídatelnost náhodného chování atomárních a subatomárních jevů, jež lze sledovat pomocí zákonů kvantové mechaniky. Jedním z nich je využití radioaktivního zdroje. Časové intervaly, ve kterých se radioaktivní zdroj rozpadá, jsou zcela nepředvídatelné. Další ze zajímavých byl i generátor Lavarand, který sestrojila firma Silicon Graphics a používal snímky lávové lampy pro generování skutečně náhodných čísel. Dnes již nefunguje. Bližší běžným možnostem je zařízení využívající špiček v síti, měření šumu anebo vstupů od uživatele, např. pohyb myši, prodleva mezi stiskem kláves a další.

Výpočetní/softwarové metody[editovat | editovat zdroj]

Generátory pseudonáhodných čísel jsou algoritmy, které vytvářejí dlouhé řetězce čísel mající zdánlivě dobré náhodné rozdělení, ale později se tyto sekvence opakují a kvalita rozdělení se snižuje. Jeden z nejpoužívanějších algoritmů je lineární kongruentní generátor fungující na základě rekurentního vztahu X_{n+1} = (a X_n + b)\, \textrm{mod}\, m. Nejvyšší počet čísel, které může vytvořit, je modulo m. Pro vyhnutí se některým nežádoucím vlastnostem lineárního kongruentního generátoru se používají lehce odlišné hodnoty násobícího koeficientu. Mezi jednoduché ručně proveditelné metody patří metoda středních čtverců navržená Johnem Von Neumannem. Její implementace je velmi jednoduchá a výsledky mají nekvalitní statistické vlastnosti.

Většina programovacích jazyků má integrovány speciální knihovny nebo funkce pro tvorbu pseudonáhodných čísel. Tyto knihovny mají povětšinou špatné statistické vlastnosti a jejich výsledky se mohou opakovat již po několika tisících vzorcích. Jako základ často používají hodiny v počítači, které obecně měří čas v milisekundách, daleko za rozeznávací schopností člověka. Poskytují proto dostatečný faktor náhodnosti pro využití např. v počítačových hrách, ale jsou nevhodné pro použití při šifrování nebo statistické analýze.

Metody podle rozdělení pravděpodobnosti[editovat | editovat zdroj]

Existuje několik metod pro generování náhodných čísel podle rozdělení pravděpodobnosti. Tyto metody transformují náhodné číslo vybrané z rovnoměrného rozdělení. Z tohoto důvodu fungují jak při generování pseudonáhodných, tak fyzikálně generovaných čísel. Jedna z metod nazývaná metoda přijetí-zamítnutí spočívá ve zvolení hodnoty x a y a testuje, zda je funkce v bodě x větší než hodnota y. Pokud je podmínka splněna, tak je hodnota x přijata, v druhém případě se algoritmus opakuje a zvolí nová x a y.

Post-processing a statistické ověření[editovat | editovat zdroj]

Ověřování výsledků i z tak věrohodných generátorů náhodných čísel, jako jsou generátory založené na kvantové mechanice, má svoji důležitost. Správná funkčnost generátorů často závisí na změnách teploty, napájecího napětí, stáří zařízení nebo venkovního rušení. Také se mohou projevit softwarové chyby v kódu programu nebo hardwarové defekty, které jsou těžce objevitelné. Generovaná čísla mohou být podrobována statistickým testům, jestli jejich zdroje fungují správně a poté vyhodnocena k vylepšení statistických vlastností algoritmů.

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Random number generation na anglické Wikipedii.