Pseudonáhodné číslo je špeciálne číslo vygenerované špeciálnym generátorom. Deterministický generátor náhodných bitov (PRNG), tiež známy ako deterministický generátor náhodných bitov (DRBG), je algoritmus na generovanie postupnosti čísel, ktorých vlastnosti sa približujú charakteristikám postupností náhodných čísel. Vygenerovaná sekvencia PRNG nie je skutočne náhodná, pretože je úplne určená hodnotou semena nazývanou seed PRNG, ktorá môže zahŕňať skutočne náhodné hodnoty. Hoci sekvencie, ktoré sú bližšie k náhodnému, možno generovať pomocou hardvérových generátorov náhodných čísel, generátory pseudonáhodných čísel sú v praxi dôležité pre rýchlosť generovania čísel a ich reprodukovateľnosť.
Aplikácia
PRNG sú ústredné pre aplikácie, ako je simulácia (napr. pre Monte Carlo), elektronické hry (napr. na generovanie procedúr) a kryptografia. Kryptografické aplikácie vyžadujú, aby výstupúdaje neboli predvídateľné z predchádzajúcich informácií. Vyžadujú sa zložitejšie algoritmy, ktoré nededia linearitu jednoduchých PRNG.
Zmluvné podmienky
Ústrednou požiadavkou na získanie PRNG sú dobré štatistické vlastnosti. Vo všeobecnosti je potrebná starostlivá matematická analýza, aby sme si boli istí, že RNG generuje čísla, ktoré sú dostatočne blízke náhodnosti, aby boli vhodné pre zamýšľané použitie.
John von Neumann varoval pred nesprávnou interpretáciou PRNG ako skutočne náhodného generátora a žartoval, že „Každý, kto zvažuje aritmetické metódy na generovanie náhodných čísel, je určite v stave hriechu.“
Použiť
PRNG je možné spustiť z ľubovoľného počiatočného stavu. Pri inicializácii v tomto stave vždy vygeneruje rovnakú sekvenciu. Perióda PRNG je definovaná takto: maximálne cez všetky počiatočné stavy dĺžky neopakujúcej sa predpony sekvencie. Obdobie je obmedzené počtom stavov, zvyčajne meraných v bitoch. Pretože sa dĺžka periódy potenciálne zdvojnásobuje s každým pridaným bitom „stavu“, je ľahké vytvoriť PRNG s periódami dostatočne veľkými pre mnohé praktické aplikácie.
Ak vnútorný stav PRNG obsahuje n bitov, jeho perióda nemôže byť väčšia ako 2n výsledkov, je oveľa kratšia. Pre niektoré PRNG je možné vypočítať trvanie bez vynechania celého obdobia. Posuvné registre s lineárnou spätnou väzbou (LFSR) sú zvyčajnesú zvolené tak, aby mali periódy rovné 2n − 1.
Lineárne kongruenciálne generátory majú periódy, ktoré možno vypočítať pomocou faktoringu. Hoci PPP zopakuje svoje výsledky po dosiahnutí konca obdobia, opakovaný výsledok neznamená, že sa dosiahol koniec obdobia, pretože jeho vnútorný stav môže byť väčší ako výstup; toto je obzvlášť zrejmé pre PRNG s jednobitovým výstupom.
Možné chyby
Chyby nájdené chybnými PRNG sa pohybujú od jemných (a neznámych) až po tie zrejmé. Príkladom je algoritmus náhodných čísel RANDU, ktorý sa na sálových počítačoch používa už desaťročia. Bol to vážny nedostatok, ale jeho nedostatočnosť zostala dlho nepovšimnutá.
V mnohých oblastiach sú výskumné štúdie, ktoré používajú náhodný výber, simulácie Monte Carlo alebo iné metódy založené na RNG, oveľa menej spoľahlivé, ako by to mohlo byť výsledkom nízkej kvality GNPG. Aj dnes je občas potrebná opatrnosť, o čom svedčí aj varovanie v Medzinárodnej encyklopédii štatistických vied (2010).
Úspešná prípadová štúdia
Ako ilustráciu zvážte široko používaný programovací jazyk Java. Od roku 2017 sa Java pri svojom PRNG stále spolieha na lineárny kongruenciálny generátor (LCG).
História
Prvý PRNG, ktorý sa vyhýba vážnym problémom a stále beží veľmi rýchlo,bol Mersenne Twister (diskutovaný nižšie), ktorý bol publikovaný v roku 1998. Odvtedy boli vyvinuté ďalšie vysoko kvalitné PRNG.
Tým sa však história pseudonáhodných čísel nekončí. V druhej polovici 20. storočia štandardná trieda algoritmov používaných pre PRNG zahŕňala lineárne kongruenciálne generátory. Bolo známe, že kvalita LCG je nedostatočná, ale lepšie metódy neboli dostupné. Press et al (2007) opísali výsledok takto: „Ak by všetky vedecké práce, ktorých výsledky sú pochybné kvôli [LCG a príbuzným] zmizli z políc knižnice, na každej poličke by bola medzera veľkosti vašej päste.“
Hlavným úspechom pri vytváraní pseudonáhodných generátorov bolo zavedenie metód založených na lineárnom rekurencii v dvojprvkovom poli; takéto oscilátory sú spojené s lineárnymi spätnoväzbovými posuvnými registrami. Slúžili ako základ pre vynález snímačov pseudonáhodných čísel.
V roku 1997 vynález od Mersena Twistera zabránil mnohým problémom s predchádzajúcimi generátormi. Mersenne Twister má periódu 219937−1 iterácií (≈4,3 × 106001). Ukázalo sa, že je rovnomerne distribuovaný v (až) 623 rozmeroch (pre 32-bitové hodnoty) a v čase svojho uvedenia bol rýchlejší ako iné štatisticky správne generátory, ktoré produkujú pseudonáhodné číselné sekvencie.
V roku 2003 predstavil George Marsaglia rodinu generátorov xorshift založených tiež na lineárnom opakovaní. Tieto generátory sú mimoriadnesú rýchle av kombinácii s nelineárnou prevádzkou prechádzajú náročnými štatistickými testami.
V roku 2006 bola vyvinutá rodina generátorov WELL. Generátory WELL v istom zmysle zlepšujú kvalitu Twister Mersenne, ktorý má príliš veľký stavový priestor a veľmi pomalú obnovu z nich, pričom generuje pseudonáhodné čísla s množstvom núl.
Kryptografia
PRNG vhodný pre kryptografické aplikácie sa nazýva kryptograficky bezpečný PRNG (CSPRNG). Požiadavkou na CSPRNG je, aby útočník, ktorý nepozná seed, mal len okrajovú výhodu v rozlíšení výstupnej sekvencie generátora od náhodnej sekvencie. Inými slovami, zatiaľ čo PRNG musí prejsť iba určitými štatistickými testami, CSPRNG musí prejsť všetkými štatistickými testami, ktoré sú obmedzené na polynomický čas vo veľkosti semena.
Aj keď dôkaz tejto vlastnosti presahuje súčasnú úroveň teórie výpočtovej zložitosti, silné dôkazy možno poskytnúť redukciou CSPRNG na problém, ktorý sa považuje za ťažký, ako je faktorizácia celého čísla. Vo všeobecnosti môže byť algoritmus certifikovaný ako CSPRNG až po rokoch kontroly.
Ukázalo sa, že je pravdepodobné, že NSA vložila asymetrické zadné dvierka do generátora pseudonáhodných čísel Dual_EC_DRBG s certifikátom NIST.
Pseudonáhodné algoritmyčísla
Väčšina algoritmov PRNG vytvára sekvencie, ktoré sú rovnomerne rozdelené niektorým z niekoľkých testov. Toto je otvorená otázka. Je to jeden z ústredných bodov v teórii a praxi kryptografie: existuje spôsob, ako rozlíšiť výstup vysokokvalitného PRNG od skutočne náhodnej sekvencie? V tomto nastavení rozlišovač vie, že bol použitý buď známy algoritmus PRNG (ale nie stav, v ktorom bol inicializovaný), alebo bol použitý skutočne náhodný algoritmus. Musí medzi nimi rozlišovať.
Bezpečnosť väčšiny kryptografických algoritmov a protokolov, ktoré používajú PRNG, je založená na predpoklade, že nie je možné rozlíšiť medzi použitím vhodného PRNG a použitím skutočne náhodnej sekvencie. Najjednoduchším príkladom tejto závislosti sú prúdové šifry, ktoré najčastejšie fungujú tak, že vynechávajú alebo odosielajú správu vo formáte obyčajného textu s výstupom PRNG, čím vytvárajú šifrový text. Navrhovanie kryptograficky adekvátnych PRNG je mimoriadne ťažké, pretože musia spĺňať dodatočné kritériá. Veľkosť jeho periódy je dôležitým faktorom kryptografickej vhodnosti PRNG, ale nie jediným.
Starý počítač PRNG navrhnutý Johnom von Neumannom v roku 1946 je známy ako metóda stredných štvorcov. Algoritmus je nasledovný: zoberte ľubovoľné číslo, odmocnite ho, odstráňte stredné číslice výsledného čísla ako „náhodné číslo“, potom použite toto číslo ako počiatočné číslo pre ďalšiu iteráciu. Napríklad umocnenie čísla 1111 dáva1234321, ktoré možno zapísať ako 01234321, 8-miestne číslo je druhou mocninou 4-miestneho čísla. To dáva 2343 ako "náhodné" číslo. Výsledok opakovania tohto postupu je 4896 atď. Von Neumann použil 10-miestne čísla, ale postup bol rovnaký.
Nevýhody „stredného štvorca“
Problém s metódou „mean square“je v tom, že všetky sekvencie sa nakoniec opakujú, niektoré veľmi rýchlo, napríklad: 0000. Von Neumann o tom vedel, ale našiel prístup, ktorý je dostatočný pre jeho účely, a obával sa, že matematické „opravy“by len skryli chyby namiesto ich odstránenia.
Von Neumann zistil, že hardvérové generátory náhodných a pseudonáhodných čísel sú nevhodné: ak nezaznamenajú vygenerovaný výstup, nemožno ich neskôr skontrolovať na chyby. Ak by si svoje výsledky zapisovali, vyčerpali by obmedzenú dostupnú pamäť počítača a tým aj schopnosť počítača čítať a zapisovať čísla. Ak by boli čísla napísané na kartách, ich písanie a čítanie by trvalo oveľa dlhšie. Na počítači ENIAC, ktorý použil, metódu "stredného štvorca" vykonal proces získavania pseudonáhodných čísel niekoľko stokrát rýchlejšie ako čítanie čísel z diernych štítkov.
Priemerný štvorec bol odvtedy nahradený zložitejšími generátormi.
Inovatívny spôsob
Nedávnou inováciou je spojenie stredného štvorca s Weilovou sekvenciou. Táto metóda zaručuje vysokú kvalitu produktovdlhé obdobie. Pomáha to získať najlepšie vzorce pseudonáhodných čísel.
