Функция $g: \mathbb{B}^* \rightarrow \mathbb{B}^*$, такая, что $g(\mathbb{B}^n) \subseteq \mathbb{B}^{m(n)}$ для некоторого полинома $m$ называется псевдослучайным генератором, если

• $g$ полиномиально вычислима
• $m(n) > n$ для всех $n \in \mathbb{N}$
• ${g(v_n)}_n$ — псевдослучайное семейство случайных величин ($v_n$ — любые равномерно распределённые случайные величины)