Введение в современную криптографию
Пренебрежительно малая вероятность успеха
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ОПРЕДЕЛЕНИЕ 3.4
| Пренебрежительно малая вероятность успеха. Пренебрежительно малая
функция - это функция, которая асимптотически меньше любой обратной по- линомиальной функции. Формально: ОПРЕДЕЛЕНИЕ 3.4 Функция f от натуральных чисел до неотрицательных действительных чисел пренебрежительно мала, если для каждого положительного многочлена p существует такое N, что для всех целых чисел n > N верно f (n) < 1/p(n). Для краткости вышесказанное можно также записать следующим образом: для каждого многочлена p и всех значительно больших значений n верно f (n) < 1/p(n). Равноценная формулировка вышесказанного требует того, что для всех постоянных c существовало такое N, что для всех n > N было верно f (n) < n−c. Обычно мы обозначаем произвольную пренебрежительно малую функцию с помощью negl (сокращение от англ. negligible). Пример 3.5 Функции 2−n, 2−√n и n− log n являются пренебрежительно малыми. Однако они стремятся к нулю по-разному. Например, мы можем рассмотреть наимень- шее значение n, для которого значение каждой функции будет меньше 1/n5: 1. Решая 2−n < n−5 , получаем n > 5 log n. Наименьшим целым значением n, для которого это верно, является n = 23. 2. Решая 2− n < n−5, получаем n > 25 log2 n. Наименьшим целым значением n, для которого это верно, является n ≈ 3500. 3. Решая n− log n < n−5, мы получаем log n > 5. Наименьшим целым значени- ем n, для которого это верно, является n = 33. ___________________________________________________________ ¹Если рассматриваемый алгоритм работает на p(n) шагах входных данных длиной n, тогда случайная лента длиной p(n) является достаточной, поскольку перехватчик может считывать максимум один случайный бит за один временной шаг. 58 Из вышесказанного у вас может сложиться впечатление, что функция n− log n стремится к нулю быстрее, чем 2-√n. Однако это не верно: для всех n > 65536 верно, что 2-√n< n− log n. Тем не менее, это не означает, что для значений n в сотнях или тысячах, вероятность успеха противника от n− log n предпочтитель- нее вероятности успеха противника от 2-√n. ♦ Техническим преимуществом работы с пренебрежительно малыми вероят- ностями успеха является то, что они подчиняются определенным свойствам за- мыкания. Далее представлено простое упражнение. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|