Pseudonáhodné číslo je speciální číslo generované speciálním generátorem. Deterministický generátor náhodných bitů (PRNG), také známý jako deterministický generátor náhodných bitů (DRBG), je algoritmus pro generování posloupnosti čísel, jejichž vlastnosti se blíží charakteristikám posloupností náhodných čísel. Vygenerovaná sekvence PRNG není skutečně náhodná, protože je zcela určena hodnotou seedu nazývanou seed PRNG, která může zahrnovat skutečně náhodné hodnoty. Přestože sekvence, které jsou blíže náhodnému, lze generovat pomocí hardwarových generátorů náhodných čísel, generátory pseudonáhodných čísel jsou v praxi důležité pro rychlost generování čísel a jejich reprodukovatelnost.
Aplikace
PRNG jsou ústřední pro aplikace, jako je simulace (např. pro Monte Carlo), elektronické hry (např. pro procedurální generování) a kryptografie. Kryptografické aplikace vyžadují výstupúdaje nebyly předvídatelné z dřívějších informací. Jsou vyžadovány složitější algoritmy, které nedědí linearitu jednoduchých PRNG.
Smluvní podmínky
Ústředním požadavkem pro získání PRNG jsou dobré statistické vlastnosti. Obecně je zapotřebí pečlivá matematická analýza, aby bylo zajištěno, že RNG generuje čísla, která jsou dostatečně blízká náhodnému, aby byla vhodná pro zamýšlené použití.
John von Neumann varoval před mylnou interpretací PRNG jako skutečně náhodného generátoru a vtipkoval, že „Každý, kdo zvažuje aritmetické metody pro generování náhodných čísel, je jistě ve stavu hříchu.“
Použít
PRNG lze spustit z libovolného počátečního stavu. Při inicializaci s tímto stavem bude vždy generovat stejnou sekvenci. Perioda PRNG je definována následovně: maximum ve všech počátečních stavech délky neopakujícího se prefixu sekvence. Perioda je omezena počtem stavů, obvykle měřených v bitech. Protože se délka periody potenciálně zdvojnásobuje s každým přidaným bitem „stavu“, je snadné vytvořit PRNG s periodami dostatečně velkými pro mnoho praktických aplikací.
Pokud vnitřní stav PRNG obsahuje n bitů, jeho perioda nemůže být delší než 2n výsledků, je mnohem kratší. U některých PRNG lze dobu trvání vypočítat bez vynechání celého období. Posuvné registry s lineární zpětnou vazbou (LFSR) jsou typickyjsou vybrány tak, aby měly periody rovné 2n − 1.
Lineární kongruenciální generátory mají periody, které lze vypočítat pomocí faktoringu. Přestože PPP své výsledky zopakuje poté, co dosáhnou konce období, opakovaný výsledek neznamená, že bylo dosaženo konce období, protože jeho vnitřní stav může být větší než výstup; to je zvláště patrné u PRNG s jednobitovým výstupem.
Možné chyby
Chyby nalezené vadnými PRNG se pohybují od jemných (a neznámých) po zjevné. Příkladem je algoritmus náhodných čísel RANDU, který se na sálových počítačích používá již desítky let. Byl to vážný nedostatek, ale jeho nedostatečnost zůstala po dlouhou dobu nepovšimnuta.
V mnoha oblastech jsou výzkumné studie, které používaly náhodný výběr, simulace Monte Carlo nebo jiné metody založené na RNG, mnohem méně spolehlivé, než by mohlo být výsledkem nekvalitního GNPG. I dnes je někdy nutná opatrnost, jak dokazuje varování v Mezinárodní encyklopedii statistické vědy (2010).
Úspěšná případová studie
Jako ilustraci uvažujme široce používaný programovací jazyk Java. Od roku 2017 se Java pro svůj PRNG stále spoléhá na lineární kongruenciální generátor (LCG).
Historie
První PRNG, který se vyhnul vážným problémům a přesto běží docela rychle,byl Mersenne Twister (diskutovaný níže), který byl zveřejněn v roce 1998. Od té doby byly vyvinuty další vysoce kvalitní PRNG.
Tím ale historie pseudonáhodných čísel nekončí. Ve druhé polovině 20. století standardní třída algoritmů používaných pro PRNG zahrnovala lineární kongruenciální generátory. Bylo známo, že kvalita LCG je nedostatečná, ale lepší metody nebyly k dispozici. Press et al (2007) popsali výsledek následovně: „Kdyby všechny vědecké práce, jejichž výsledky jsou kvůli [LCG a souvisejícím] zpochybněny, zmizely z regálů knihoven, na každé polici by byla mezera o velikosti vaší pěsti.“
Hlavním úspěchem při vytváření pseudonáhodných generátorů bylo zavedení metod založených na lineárním rekurentu ve dvouprvkovém poli; takové oscilátory jsou připojeny k lineárním zpětnovazebním posuvným registrům. Sloužily jako základ pro vynález senzorů pseudonáhodných čísel.
Zejména vynález Mersena Twistera z roku 1997 se vyhnul mnoha problémům s dřívějšími generátory. Mersenne Twister má periodu 219937−1 iterací (≈4,3 × 106001). Bylo prokázáno, že je rovnoměrně distribuován v (až) 623 dimenzích (pro 32bitové hodnoty) a v době svého zavedení byl rychlejší než jiné statisticky správné generátory, které produkují pseudonáhodné číselné sekvence.
V roce 2003 představil George Marsaglia rodinu generátorů xorshift také založených na lineárním opakování. Tyto generátory jsou extrémnějsou rychlé a – v kombinaci s nelineární operací – procházejí přísnými statistickými testy.
V roce 2006 byla vyvinuta řada generátorů WELL. Generátory WELL v jistém smyslu zlepšují kvalitu Twister Mersenne, který má příliš velký stavový prostor a velmi pomalé zotavení z něj, generuje pseudonáhodná čísla s mnoha nulami.
Kryptografie
PRNG vhodný pro kryptografické aplikace se nazývá kryptograficky bezpečný PRNG (CSPRNG). Požadavek na CSPRNG je, že útočník, který nezná seed, měl pouze okrajovou výhodu v rozlišení výstupní sekvence generátoru od náhodné sekvence. Jinými slovy, zatímco PRNG musí projít pouze určitými statistickými testy, CSPRNG musí projít všemi statistickými testy, které jsou omezeny na polynomiální čas ve velikosti semene.
Přestože důkaz této vlastnosti přesahuje současnou úroveň teorie výpočetní složitosti, silný důkaz lze poskytnout redukcí CSPRNG na problém, který je považován za těžký, jako je celočíselná faktorizace. Obecně mohou být vyžadovány roky přezkoumání, než bude možné algoritmus certifikovat jako CSPRNG.
Ukázalo se, že je pravděpodobné, že NSA vložila asymetrická zadní vrátka do generátoru pseudonáhodných čísel Dual_EC_DRBG certifikovaného NIST.
Pseudonáhodné algoritmyčísla
Většina algoritmů PRNG vytváří sekvence, které jsou rovnoměrně rozloženy některým z několika testů. Toto je otevřená otázka. Je to jeden z ústředních bodů v teorii a praxi kryptografie: existuje způsob, jak odlišit výstup vysoce kvalitního PRNG od skutečně náhodné sekvence? V tomto nastavení překladač ví, že byl použit buď známý algoritmus PRNG (ale nikoli stav, ve kterém byl inicializován), nebo byl použit skutečně náhodný algoritmus. Musí mezi nimi rozlišovat.
Bezpečnost většiny kryptografických algoritmů a protokolů, které používají PRNG, je založena na předpokladu, že není možné rozlišit mezi použitím vhodného PRNG a použitím skutečně náhodné sekvence. Nejjednoduššími příklady této závislosti jsou proudové šifry, které nejčastěji fungují tak, že vynechají nebo odešlou zprávu ve formátu prostého textu s výstupem PRNG, čímž vytvoří šifrový text. Navrhování kryptograficky adekvátních PRNG je extrémně obtížné, protože musí splňovat další kritéria. Velikost jeho období je důležitým faktorem kryptografické vhodnosti PRNG, ale ne jediným.
Starý počítač PRNG navržený Johnem von Neumannem v roce 1946 je známý jako metoda středních čtverců. Algoritmus je následující: vezměte libovolné číslo, odmocněte ho, odstraňte střední číslice výsledného čísla jako „náhodné číslo“, poté použijte toto číslo jako počáteční číslo pro další iteraci. Například umocnění čísla 1111 dává1234321, které lze zapsat jako 01234321, 8místné číslo je druhou mocninou 4místného čísla. To dává 2343 jako "náhodné" číslo. Výsledek opakování tohoto postupu je 4896 a tak dále. Von Neumann použil 10místná čísla, ale postup byl stejný.
Nevýhody „středního čtverce“
Problém s metodou „středního čtverce“je v tom, že všechny sekvence se nakonec opakují, některé velmi rychle, například: 0000. Von Neumann o tom věděl, ale našel pro jeho účely dostačující přístup a obával se, že matematické „opravy“by jen skryly chyby, místo aby je odstranily.
Von Neumann shledal hardwarové generátory náhodných a pseudonáhodných čísel nevhodnými: pokud nezaznamenají vygenerovaný výstup, nelze je později zkontrolovat na chyby. Pokud by si své výsledky zapisovali, vyčerpali by omezenou dostupnou paměť počítače a tím i schopnost počítače číst a zapisovat čísla. Pokud by se čísla psala na karty, jejich zápis a čtení by trvalo mnohem déle. Na počítači ENIAC, který použil, metodu „středního čtverce“a provedl proces získávání pseudonáhodných čísel několik setkrát rychleji než čtení čísel z děrných štítků.
Střední čtverec byl od té doby nahrazen složitějšími generátory.
Inovativní metoda
Nedávnou inovací je kombinace středního čtverce s Weilovou sekvencí. Tato metoda zajišťuje vysokou kvalitu produktů uvnitřdlouhá doba. Pomáhá získat nejlepší vzorce pseudonáhodných čísel.
