Pseudorandomnost - Pseudorandomness
Pseudonáhodná posloupnost čísel, je ten, který se zdá být statisticky náhodné , i přesto, že byl vyroben zcela deterministický a opakovatelný proces.
Pozadí
Generování náhodných čísel má mnoho využití, například pro náhodné vzorkování , metody Monte Carlo , deskové hry nebo hazardní hry . Ve fyzice je však většina procesů, jako je gravitační zrychlení, deterministická, což znamená, že vždy vytvářejí stejný výsledek ze stejného výchozího bodu. Některé pozoruhodné výjimky jsou radioaktivní rozpad a kvantové měření , které jsou modelovány jako skutečně náhodné procesy v základní fyzice. Protože tyto procesy nejsou praktickými zdroji náhodných čísel, lidé používají pseudonáhodná čísla, která v ideálním případě mají nepředvídatelnost skutečně náhodné sekvence, přestože jsou generována deterministickým procesem.
V mnoha aplikacích je deterministickým procesem počítačový algoritmus nazývaný generátor pseudonáhodných čísel , kterému musí být nejprve poskytnuto číslo nazývané náhodné semeno . Vzhledem k tomu, že stejné semeno poskytne pokaždé stejnou sekvenci, je důležité, aby bylo osivo dobře vybráno a skryto, a to zejména v bezpečnostních aplikacích, kde je nepředvídatelnost vzoru kritickou vlastností.
V některých případech, kdy je důležité, aby byla sekvence prokazatelně nepředvídatelná, lidé použili fyzické zdroje náhodných čísel, jako je radioaktivní rozpad, atmosférický elektromagnetický šum získávaný z rádia naladěného mezi stanicemi nebo smíšené časování úhozů lidí . Časová investice potřebná k získání těchto čísel vede ke kompromisu: použití některých z těchto fyzikálních údajů jako zárodku generátoru pseudonáhodných čísel.
Dějiny
Před moderní výpočetní technikou by vědci požadující náhodná čísla buď je vygenerovali různými prostředky ( kostky , karty , ruleta atd.), Nebo použili stávající tabulky náhodných čísel.
První pokus poskytnout vědcům připravenou zásobu náhodných číslic byl v roce 1927, kdy Cambridge University Press zveřejnila tabulku 41 600 číslic vyvinutou LHC Tippett . V roce 1947 generovala RAND Corporation čísla elektronickou simulací rulety; výsledky byly nakonec publikovány v roce 1955 jako A Million Random Digits with 100,000 Normal Deviates .
Ve výpočetní složitosti
V teoretické informatiky , je distribuce je pseudorandom proti třídě protivníků není-li protivník ze skupiny jej odlišit od rozdělení rovnoměrné s významnou výhodu. Tento pojem pseudorandomnosti je studován v teorii výpočetní složitosti a má aplikace v kryptografii .
Formálně nechť S a T jsou konečné množiny a nechť F = { f : S → T } je třída funkcí. Distribuce D přes S je ε- pseudonáhodné proti F -li pro každou f v F , na statistické vzdálenost mezi distribucí a , kde a je od vzorku D , a , kde a je odebrán vzorek z rovnoměrné rozložení na S , je nejvýše e .
V typických aplikacích, třída F popisuje model výpočtu se omezených zdrojů a jeden má zájem na navrhování rozvodů D s určitými vlastnostmi, které jsou pseudorandom proti F . Distribuce D je často specifikována jako výstup pseudonáhodného generátoru .
Viz také
- Kryptograficky bezpečný generátor pseudonáhodných čísel
- Seznam generátorů náhodných čísel
- Pseudonáhodná binární sekvence
- Pseudonáhodný soubor
- Generátor pseudonáhodných čísel
- Kvazi-náhodná sekvence
- Generování náhodných čísel
- Pseudonáhodný hluk
Reference
- ^ a b George Johnson (12. června 2001). „Znalci chaosu nabízejí cenný produkt: náhodnost“ . The New York Times .
-
^ SP Vadhan (2012). Pseudorandomnost .
pseudorandomnost, teorie efektivního generování objektů, které „vypadají náhodně“, přestože byly konstruovány s použitím malé nebo žádné náhodnosti
- ^ Mark Ward (09.08.2015). „Náhodná čísla webu jsou příliš slabá, varují vědci“ . BBC .
- ^ Jonathan Knudson (leden 1998). „Javatalk: podkovy, ruční granáty a náhodná čísla“. Sun Server . s. 16–17.
- ^ a b „Milion náhodných číslic“ . RAND Corporation . Citováno 30. března 2017 .
- ^ Oded Goldreich. Výpočetní složitost: koncepční perspektiva. Cambridge University Press. 2008.
- ^ „Pseudorandomnost“ (PDF) .
Další čtení
- Donald E. Knuth (1997) The Art of Computer Programming , Volume 2: Seminumerical Algorithms (3rd edition) . Addison-Wesley Professional, ISBN 0-201-89684-2
- Oded Goldreich. (2008) Computational Complexity: a conceptual perspective . Cambridge University Press. ISBN 978-0-521-88473-0 . (Omezený náhled v Knihách Google)
- Vadhan, SP (2012). „Pseudorandomnost“. Základy a trendy v teoretické informatice . 7 (1–3): 1–336. doi : 10,1561/0400000010 .
externí odkazy
- HotBits: Originální náhodná čísla generovaná radioaktivním rozpadem
- Používání a vytváření náhodných čísel v kryptografické kvalitě
- V RFC 1750 je použití sekvencí pseudonáhodných čísel v kryptografii podrobně diskutováno.