Paradigmy pre nepodmienené pseudonáhodné generátory

Pôvodný názov:

Paradigms for Unconditional Pseudorandom Generators

Obsah knihy:

V tomto komplexnom prehľade nepodmienených pseudonáhodných generátorov (PRG) autori predstavujú čitateľovi intuitívny úvod do niektorých najdôležitejších rámcov a techník na konštrukciu nepodmienených PRG pre obmedzené modely výpočtov. Autori rozoberajú štyri hlavné paradigmy na konštrukciu PRG: niekoľko PRG založených na k-rovnomerných generátoroch, generátoroch s malou odchýlkou a ich jednoduchých kombináciách, niekoľko PRG založených na „recyklácii“ náhodných bitov s cieľom využiť komunikačné úzke miesta, súvislosti medzi PRG a výpočtovou tvrdosťou a rámce PRG založené na náhodných obmedzeniach.

Autori vysvetľujú, ako použiť tieto paradigmy na konštrukciu PRG, ktoré fungujú bezpodmienečne, bez nedokázaných matematických predpokladov. Konštrukcie PRG využívajú také zložky, ako sú aritmetika konečného poľa, expanzné grafy a extraktory náhodnosti.

Analýzy využívajú techniky ako Fourierova analýza, sendvičové aproximátory a lemy o zjednodušení pod obmedzením. Paradigmy nepodmienených pseudonáhodných generátorov ponúkajú čitateľovi základy dôležitej témy, ktorá sa široko využíva v teoretickej informatike a kryptografii.