Список обозначений
Генератор для семейства функций
generator for a function family
Пусть $N$ — подмножество $\mathbb N$. Пусть также при всех $n\in N$ определено непустое конечное множество $D_n\subseteq\{0,1\}^*$. Предположим, что каждой паре $(n,d)$, где $n\in N$ и $d\in D_n$, поставлена в соответствие функция $f_{n,d}\colon X_{n,d}\to\{0,1\}^*$, где $X_{n,d}\subseteq\{0,1\}^*$. Тогда пара полиномиальных алгоритмов $(\mathcal G,\mathcal E)$ называется генератором для семейства функций $(f_{n,d}\,|\, n\in N,\, d\in D_n)$, если - $\mathcal G$ — вероятностный алгоритм, а $\mathcal E$ — детерминированный;
- для любого $n\in N$ случайная величина $\mathcal G(1^n)$ распределена равномерно на $D_n$;
- $\mathcal E(1^n,d,x)=f_{n,d}(x)$ для любых $n\in N$, $d\in D_n$ и $x\in X_{n,d}$.
Понятие генератора для семейства функций носит технический характер и предназначено для определения генератора псевдослучайных функций, генератора псевдослучайных перестановок и генератора сильно псевдослучайных перестановок.