$\mathbb N$ — множество всех целых неотрицательных чисел;

$\mathbb Z_m$ — множество $\{0,\dots,m-1\}$, являющееся ассоциативным коммутативным кольцом с единицей относительно арифметических операций по модулю $m$ ($m\in\mathbb N\setminus\{0\}$);

$\mathbb Z^{\star}_m$ — группа всех обратимых элементов кольца $\mathbb Z_m$, состоящая из всех $x\in\mathbb Z_m$, взаимно простых с $m$ ($m\in\mathbb N\setminus\{0\}$);

$X^n$ — $n$-я декартова степень множества $X$ (в частности, $\{0,1\}^n$ — множество всех двоичных строк длины $n$);

$X^*=\bigcup_{n=0}^\infty X^n$ (в частности, $\{0,1\}^*$ — множество всех двоичных строк);

$\#X$ — мощность конечного множества $X$;

$\operatorname{Fun}(X,Y)$ — множество всех функций из множества $X$ в множество $Y$;

$\operatorname{Per}(X)$ — множество всех перестановок множества $X$;

$f(n)=\Omega(g(n))$ при $n\in N$ означает, что $g=O(f)$ при $n\in N$ ($f,g\colon N\to\{r\in\mathbb R\,|\, r\geqslant0\}$, где $N$ — бесконечное подмножество $\mathbb N$);

$f(n)=\omega(g(n))$ при $n\in N$ означает, что $g=o(f)$ при $n\in N$ ($f,g\colon N\to\{r\in\mathbb R\,|\, r\geqslant0\}$, где $N$ — бесконечное подмножество $\mathbb N$);

$\oplus$ — операция сложения по модулю $2$;

$1^n$ — строка из $n$ единиц ($n\in\mathbb N$);

$x_{[i]}$ — $i$-й бит строки $x\in\{0,1\}^*$;

$x_{[i,\dots,j]}$ — строка $x_{[i]}x_{[i+1]}\dots x_{[j]}$, если $1\leqslant i\leqslant j\leqslant\lvert{x}\rvert$, и пустая строка в противном случае ($x\in\{0,1\}^*$);

$\lvert{x}\rvert$ — длина строки $x\in\{0,1\}^*$;

$\operatorname{num}(x)$ — целое положительное число с двоичной записью $1x$, т. е. $2^l+\sum_{i=1}^lx_{[i]}2^{l-1}$, где $x\in\{0,1\}^*$ и $l=\lvert{x}\rvert$ (очевидно, что $x\mapsto\operatorname{num}(x)$ — биекция $\{0,1\}^*$ на множество всех целых положительных чисел).

$\mathop{\mathrm{supp}}$ — носитель распределения вероятностей или случайной величины с конечным или счетным носителем;

$x\leftarrow\mathfrak D$ означает что $x$ — случайный элемент, выбранный относительно распределения вероятностей $\mathfrak D$ на некотором конечном или счетном множестве;

$x\leftarrow\widetilde x$ означает что $x$ — случайное значение случайной величины $\widetilde x$ с конечным или счетным носителем (в одной и той же формуле выбор случайных значений нескольких случайных величин осуществляется слева направо);

$x\in_{\mathfrak U} X$ означает что $x$ — случайный элемент непустого конечного множества $X$ относительно равномерного распределения вероятностей на этом множестве (другими словами, это обозначение эквивалентно $x\leftarrow\mathfrak U(X)$, где $\mathfrak U(X)$ — равномерное распределение на непустом конечном множестве $X$);

$\widetilde u_n$ — случайная величина, распределенная равномерно на $\{0,1\}^n$ ($n\in\mathbb N$);

$\mathcal A(\dots;r)$ означает, что вероятностный алгоритм $\mathcal A$ использует двоичную строку $r$ в качестве источника случайных битов;

$\mathcal A^{B_1,\dots,B_k}(x)$ — случайная величина, представляющая собой результат вычисления вероятностного алгоритма $\mathcal A$ на входе $x$ с использованием оракулов $B_1,\dots,B_k$ (последние могут отсутствовать; кроме того, оракул, возвращающий в ответ на запрос $y$ значение некоторой функции на $y$, обозначается так же, как эта функция);

$\langle{\mathcal A(y),\mathcal B(z)}\rangle(x)$ — случайная величина, представляющая собой выходное значение алгоритма $\mathcal B$, полученное в результате совместного вычисления интерактивных вероятностных алгоритмов $\mathcal A$ и $\mathcal B$ при условии, что $y$ и $z$ — входы алгоритмов $\mathcal A$ и $\mathcal B$ соответственно, а $x$ — общий вход этих алгоритмов;

$\operatorname{mess}^{\mathcal A(y)}_{\mathcal B(z)}(x)$ — случайная величина, состоящая из последовательности сообщений, полученных алгоритмом $\mathcal B$ в результате совместного вычисления интерактивных вероятностных алгоритмов $\mathcal A$ и $\mathcal B$ при условии, что $y$ и $z$ — входы алгоритмов $\mathcal A$ и $\mathcal B$ соответственно, а $x$ — общий вход этих алгоритмов;

$\operatorname{view}^{\mathcal A(y)}_{\mathcal B(z)}(x)$ — случайная величина, состоящая из значения $r$ случайной строки алгоритма $\mathcal B$ и последовательности $\operatorname{mess}^{\mathcal A(y)}_{\mathcal B(z;r)}(x)$ сообщений, полученных этим алгоритмом в результате совместного вычисления интерактивных вероятностных алгоритмов $\mathcal A$ и $\mathcal B$ при условии, что $y$ и $z$ — входы алгоритмов $\mathcal A$ и $\mathcal B$ соответственно, $x$ — общий вход этих алгоритмов, а $r$ — случайная строка алгоритма $\mathcal B$.

Под полиномом понимается произвольная функция $p\colon\mathbb N\to\{r\in\mathbb R\,|\, r>0\}$ такая, что $p(n)=cn^d$ для всех $n\in\mathbb N\setminus\{0\}$, где $c>0$ и $d\geqslant0$ — константы. Случайные величины, как правило, обозначаются символами с тильдой, распределения вероятностей — готическими буквами, а алгоритмы — рукописными буквами. Если не оговорено противное, то вводимые случайные величины предполагаются независимыми от всех других. Выборы случайных элементов также осуществляется независимо, если противное не оговорено явно и не вытекает из контекста.

Под словом «алгоритм» мы понимаем вычислитель в однородной модели вычислений, т. е. машину Тьюринга. Таким образом, вычислитель в неоднородной модели вычислений алгоритмом не считается (этот вычислитель можно считать семейством алгоритмов). Это согласуется с тезисом Чёрча, а также с тем фактом, что в неоднородной модели вычислений эффективно решаются даже некоторые алгоритмически неразрешимые проблемы. Подробнее см. статьи, посвященные однородной и неоднородной моделям вычислений.

Изложение в справочнике почти всегда ведется в терминах алгоритмов, т. е. в однородной модели вычислений. Однако многие определения легко переформулировать для неоднородной модели вычислений. Подчеркнем, что при этом следует переносить в неоднородную модель лишь вычислительные ресурсы противника. В качестве примера см. переформулировку для неоднородной модели вычислений определения односторонней функции в статье, посвященной таким функциям.

Как обычно, мы предполагаем, что все дискретные объекты, с которыми работают алгоритмы, отождествляются со строками из $\{0,1\}^*$. При этом длиной объекта называется длина соответствующей строки. В частности, если не оговорено противное, целые числа предполагаются заданными своими двоичными записями со старшим битом $1$.

Если в одну формулу входят несколько одинаковых символов случайной величины, то они обозначают одну и ту же случайную величину. Например, пусть $R$ — бинарный предикат на некотором конечном или счетном множестве $X$, а $\widetilde x$ — случайная величина, принимающая значения в $X$. Тогда $\Pr(R(\widetilde x,\widetilde x)=1)$ обозначает то же самое, что $\Pr(R(x,x)=1)$ при $x\leftarrow\widetilde x$, т. е. $\Pr(\widetilde x\in\{x\in X\,|\, R(x,x)=1\})$.

В описаниях полиномиальных алгоритмов, встречающихся в литературе, часто встречаются действия вида $x\in_{\mathfrak U} X$, где $X$ — непустое конечное множество, заданное в некотором смысле эффективно (например, $X=\{1,\dots,m\}$, $X=\mathbb Z^{\star}_m$ и т. п.) Но если $\#X$ не является степенью двойки, то это действие невыполнимо с помощью вероятностного алгоритма, использующего ограниченное (для данного множества $X$) число случайных битов. В то же время во многих важных случаях за полиномиальное от $\log\#X$ время можно породить распределение вероятностей такое, что статистическое расстояние между этим распределением и равномерным распределением на $X$ не превосходит $2^{-q(\log\#X)}$, где $q$ — произвольный наперед заданный полином. В этих случаях, допуская вольность речи, можно считать, что вышеуказанные действия выполнимы за полиномиальное время.

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна