Введение в современную криптографию


Пренебрежительно малая вероятность успеха



Pdf көрінісі
бет37/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   33   34   35   36   37   38   39   40   ...   249
Криптография Катц

Пренебрежительно малая вероятность успеха. Пренебрежительно малая 
функция - это функция, которая асимптотически меньше любой обратной по-
линомиальной функции. Формально:
ОПРЕДЕЛЕНИЕ 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. 

Техническим преимуществом работы с пренебрежительно малыми вероят-
ностями успеха является то, что они подчиняются определенным свойствам за-
мыкания. Далее представлено простое упражнение.


Достарыңызбен бөлісу:
1   ...   33   34   35   36   37   38   39   40   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет