Часто в приложениях бывает так, что нельзя сделать так, чтобы функция была везде определена. (Например, функция, определенная только на произведении двух больших чисел.) Часто бывает нужно выбрать случайный элемент из области определения.

***

#### Определение
Пусть $\mu_n$ - случайная величина со значениями в $\{0, 1\}^{k(n)}$. Будем говорить, что $\mu_n$ - **полиномиально вычислимая**, если существует такой полиномиальный вероятностный алгоритм $S$ с пустым входом, что $\forall x \in \{0, 1\}^{k(n)}\ Pr\{S(\varepsilon) = x\} = Pr\{\mu_n = x\}$

***

#### Определение
**Статистическое расстояние**: $dist(\mu_n, \nu_n) = max_{T \subset \{0, 1\}^{k(n)}} |Pr\{\mu_n \ in T \} - Pr\{\nu_n \in T \}| = \sum_{x \ in \{0, 1\}^{k(n)}} \frac{1}{2}|Pr\{\mu_n = x \} - Pr\{\nu_n = x \}|$

***

#### Определение
Случайная величина $\mu_n$ **доступна**, если $$\exists \nu_n\ \forall p(\cdot)\ \exists N\ \forall n > N dist(\mu_n, \nu_n) < \frac{1}{p(n)}$$
где $\nu_n$ -- некоторая полиномиально вычислимая случайная величина.

***

#### Определение
Функция $f \colon D \rightarrow \{0, 1\}^n$ называется **частичной односторонней**, если:
-   Равномерная случайная величина на $D$ доступна
-   $f$ вычислима за полиномиальное время
-   $\forall R_n\ \forall p(\cdot)\ \exists N\ \forall n > N\ Pr_{x \in D}\{R_n(f(x)) \in D, f(R_n(f(x))) = f(x)\} < \frac{1}{p(n)}$

***

#### *Предположительно* частично односторонние функции:

-   Функция Рабина: $(x, y) \rightarrow (x^2\ mod\ y, y)$, где
    $y = p \cdot q$,
    $p_n, q$ - простые вида $4k + 3$, а 
    $x$ - квадратичный вычет.

-   Функция RSA: $(x, y, z) \rightarrow (x^z\ mod\ y, y, z)$ - извлечение корня степени $z$ 
    $y = p \cdot q$ 
    $x$ - вычет, взаимно простый с $y$ 
    $z$ - взаимно просто с $\phi(p\cdot q) = (p - 1)(q - 1)$

-   Дискретная экспонента $(x, y, z) \rightarrow (x, y, x^z)$ - логарифм по основанию $x$.