Generátor náhodných čísel (často zkráceně RNG) je výpočetní nebo fyzikální zařízení, které je navrženo tak, aby generovalo posloupnost čísel nebo symbolů, které postrádají jakýkoli vzor, tj. vypadají náhodně. Počítačové systémy pro generování náhodných čísel jsou široce používány, ale často tomuto cíli nedosahují, i když mohou splnit některé statistické testy náhodnosti, které mají zajistit, že nemají žádné snadno rozpoznatelné vzory. Metody pro generování náhodných výsledků existují již od starověku, včetně kostek, házení mincí, míchání hracích karet, používání yarrow stonků v I-ťingu a mnoha dalších technik.
„Pravda“ náhodná čísla vs. pseudonáhodná čísla
Pro generování náhodných čísel se používají dvě hlavní metody. Jedna měří nějaký fyzikální jev, u kterého se očekává, že bude náhodný, a pak kompenzuje možné odchylky v procesu měření. Druhá používá výpočetní algoritmy, které produkují dlouhé sekvence zdánlivě náhodných výsledků, které jsou ve skutečnosti určeny kratším počátečním osivem nebo klíčem. Druhý typ se často nazývá pseudo-náhodné generátory čísel.
„Generátor náhodných čísel“ založený výhradně na deterministických výpočtech nemůže být považován za „pravý“ generátor náhodných čísel, protože jeho výstup je ze své podstaty předvídatelný. John von Neumann proslul výrokem „Každý, kdo používá aritmetické metody k výrobě náhodných čísel, je ve stavu hříchu.“ Jak odlišit „pravé“ náhodné číslo od výstupu generátoru pseudonáhodných čísel je velmi obtížný problém. Nicméně pečlivě zvolené generátory pseudonáhodných čísel mohou být použity místo pravých náhodných čísel v mnoha aplikacích. Důsledná statistická analýza výstupu je často potřebná, aby měla důvěru v algoritmus.
Náhodná čísla ve výpočetní technice
Většina počítačových programovacích jazyků obsahuje funkce nebo knihovní rutiny, které se vydávají za generátory náhodných čísel. Často jsou navrženy tak, aby poskytovaly náhodný byte nebo slovo nebo číslo s plovoucí desetinnou čárkou rovnoměrně rozložené mezi 0 a 1.
Generování náhodných čísel z fyzikálních procesů
Panuje všeobecná shoda, že pokud existují takové věci jako „pravdivá“ náhodná čísla, je nejpravděpodobnější, že se najdou při pohledu na fyzikální procesy, které jsou, pokud víme, nepředvídatelné.
Fyzický generátor náhodných čísel může být založen na v podstatě náhodném atomovém nebo subatomárním fyzikálním jevu, jehož náhodnost lze vysledovat až k zákonům kvantové mechaniky. Příkladem toho je herní konzole Atari, která používala šum z analogového obvodu pro generování skutečných náhodných čísel. Dalšími příklady jsou radioaktivní rozpad, tepelný šum, šum výstřelu a posun hodin.
Pro zajištění určitého stupně náhodnosti mezi specializovaným hardwarem na jedné straně a generováním algoritmů na straně druhé vyžaduje určitý počítačový software související s bezpečností, aby uživatel zadal dlouhý řetězec pohybů myší nebo vstup klávesnicí.
Následné zpracování a statistické kontroly
Náhodná čísla rovnoměrně rozložená mezi 0 a 1 lze použít pro generování náhodných čísel libovolného požadovaného rozdělení jejich předáním inverzní distribuční funkci požadovaného rozdělení. Pro generování dvojice nezávislých standardních normálně rozložených náhodných čísel (x, y) lze nejprve vygenerovat polární souřadnice (r, θ), kde r~χ22 a θ~UNIFORM(0,2π) (viz Box-Mullerova transformace).
Některé 0 až 1 RNG obsahují 0, ale vylučují 1, zatímco jiné obsahují nebo vylučují obě.
Výstupy více nezávislých RNG lze kombinovat (například pomocí bitové operace XOR) tak, aby kombinovaná RNG byla alespoň tak dobrá jako ta nejlepší používaná RNG. Více podrobností o nekorelovaných poblíž náhodných bitových proudů.
Výpočetní a hardwarové generátory náhodných čísel se někdy kombinují, aby odrážely výhody obou druhů. Výpočetní generátory náhodných čísel mohou obvykle generovat pseudonáhodná čísla mnohem rychleji, než fyzické generátory mohou generovat skutečnou náhodnost.
Generátory náhodných čísel mají několik důležitých aplikací v oblasti hazardních her, statistického vzorkování, počítačové simulace, kryptografie atd.
Všimněte si, že obecně tam, kde je nepředvídatelnost prvořadá – například v bezpečnostních aplikacích – jsou hardwarové generátory obecně preferovány tam, kde je to proveditelné, před pseudonáhodnými algoritmy.
Sekvence s nízkými nesrovnalostmi jako alternativa
Některé výpočty využívající generátor náhodných čísel lze shrnout jako výpočet celkové nebo průměrné hodnoty, například výpočet integrálů metodou Monte Carlo. Pro takové problémy může být možné najít přesnější řešení použitím takzvaných sekvencí s nízkými nesrovnalostmi, nazývaných také kvasirandomí čísla. Takové sekvence mají určitý vzor, který vyplňuje mezery rovnoměrně, kvalitativně řečeno; skutečně náhodná sekvence může, a obvykle to dělá, zanechat větší mezery.
Generace z pravděpodobnostního rozdělení
Existuje několik metod, jak vygenerovat náhodné číslo na základě funkce rozdělení pravděpodobnosti. Tyto metody zahrnují transformaci normálního náhodného čísla nějakým způsobem – kvůli tomu tyto metody fungují stejně dobře při generování pseudonáhodných i pravdivých náhodných čísel. Jedna metoda, nazývaná inverzní metoda, zahrnuje integraci až do plochy větší nebo rovné náhodnému číslu (které by mělo být vygenerováno mezi 0 a 1 pro správné rozdělení). Druhá metoda, nazývaná metoda přijetí-odmítnutí, zahrnuje výběr hodnoty x a y a testování, zda je funkce x větší než hodnota y – pokud je přijímá hodnotu x, pokud ne reguluje hodnotu x a zkouší to znovu.
Náhodná čísla dostupná přes internet a od stran, které uživatel specificky nezná a kterým důvěřuje, by neměla být používána kryptograficky.