Generátor náhodných čísel

Generátor náhodných čísel je proces, který vytváří absolutně náhodnou sekvenci, která postrádá jakýkoliv vzor (sekvenci, předvídatelnost). Tím se liší od generátoru pseudonáhodných čísel používaného v počítačích.

Praktické využití a aplikace

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ým vytvářejícím pseudonáhodná čísla.

Dobrým generátorem náhodných čísel může být i člověk (mozek),^[1][2] aniž by zde bylo riziko, zda nejsou implementována zadní vrátka.

Pravá náhodná vs. pseudonáhodná čísla

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í

Fyzikální/hardwarové metody

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

Využít lze i náhodnosti krystalizace.^[3]

Výpočetní/softwarové metody

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 ${\displaystyle X_{n+1}=(aX_{n}+b)\,{\textrm {mod}}\,m}$. Nejvyšší počet čísel, které může vytvořit, je modulo ${\displaystyle 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 prostředku čtverce 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

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í

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é. Generátory náhodných čísel tedy snadno mohou obsahovat zadní vrátka, takže je nutná důvěra ve výrobce. 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ů. Ovšem ani na certifikaci náhodnosti se nelze spolehnout.^[4]

Reference

Související články

• Generátor pseudonáhodných čísel
• Lineární kongruentní generátor
• Hardwarový generátor náhodných čísel

Externí odkazy

• HotBits - ukázka pravého generátoru čísel
• Článek o Lavarand na Anglické Wikipedii

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