Generátor pseudonáhodných čísel: Porovnání verzí

Pseudonáhodné generátory, ať už čísel či binárních posloupností, lze elegantně realizovat použitím [[jednosměrná funkce|jednosměrných funkcí]], na jejichž inverzi v současnosti není znám žádný efektivní algoritmus. V takovém případě postačí, když za „random seed“ vezmeme relativně malé číslo, pak iterativně aplikujeme jednosměrnou funkci a do pseudonáhodné posloupnosti postupně zařazujeme [[hard-core predikát|hard-core bity]] pro tyto iterace. Tak dostaneme pseudonáhodnou binární posloupnost, která může být [[polynom]]iálně delší, než náhodný vstup. Ukázkovým příkladem pseudonáhodného generátoru, založeném na předpokladu nemožnosti efektivní [[faktorizace]], je [[Blum Blum Shub|Blum-Blum-Shub]] pseudonáhodný generátor. Ten je možno použít na konstrukci [[Šifrovací algoritmus Blum-Goldwasser|Blum-Goldwasser]] kryptosystému s veřejným klíčem. To je [[proudová šifra]], ve které je zpráva šifrovánášifrována spočítanímspočítáním jejího [[XOR]]u s pseudonáhodně vygenerovaným tajným [[šifrovací klíč|klíčem]] stejné délky, tak jako je tomu u [[Vernamova šifra|Vernamovy šifry]].

Chyby vyskytující se ve vadných generátorech pseudonáhodných čísel se objevují od těch nejnepatrnějších (a neznámých) až ke zřejmým. Jako příklad může být uveden [[RANDU]], což je algoritmus náhodných čísel, používaný po celá desetiletí na [[Mainframemainframe]]ch. Tento algoritmus byl vskutku nedostatečný, ale jeho neadekvátnost zůstala bez povšimnutí po celá léta. V mnoha oborech, bylo velké množství výzkumných prací té doby, která se spoléhala na náhodný výběr nebo na [[Metoda Monte Carlo|metodu Monte Carlo]], jinak řečeno jsou méně spolehlivé než by mohly být v případě výsledků.<ref name="press92">{{cite book |author=Press, William H., et al. |year=1992 |title=[[Numerical Recipes]] in Fortran 77: The Art of Scientific Computing |edition=2nd |isbn=0-521-43064-X}}</ref>