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é

Reference

  1. ^ a b George Johnson (12. června 2001). „Znalci chaosu nabízejí cenný produkt: náhodnost“ . The New York Times .
  2. ^ 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
  3. ^ Mark Ward (09.08.2015). „Náhodná čísla webu jsou příliš slabá, varují vědci“ . BBC .
  4. ^ Jonathan Knudson (leden 1998). „Javatalk: podkovy, ruční granáty a náhodná čísla“. Sun Server . s. 16–17.
  5. ^ a b „Milion náhodných číslic“ . RAND Corporation . Citováno 30. března 2017 .
  6. ^ Oded Goldreich. Výpočetní složitost: koncepční perspektiva. Cambridge University Press. 2008.
  7. ^ „Pseudorandomnost“ (PDF) .

Další čtení

externí odkazy