Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
  Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 14.1.2 Односторонние функции в теории сложности Вверх: 14.1 Односторонние функции Назад: 14.1 Односторонние функции   Содержание   Предметный указатель

14.1.1 Модели вычислений

Под эффективными алгоритмами всюду ниже, согласно тезису Эдмондса, мы будем понимать полиномиальные алгоритмы. Последние, в соответствии с подходом, принятым в теоретической криптографии, можно определить в двух моделях вычислений.

В однородной (uniform) модели вычислений полиномиальный алгоритм -- это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входного слова.

В неоднородной (nonuniform) модели под алгоритмом понимается семейство булевых схем $ \{C_n\}$. Схема $ C_n$ имеет $ n$ входов и построена, скажем для определенности, из функциональных элементов И, ИЛИ и НЕ. Без ограничения общности можно считать, что все элементы И и ИЛИ двухвходовые. Алгоритм $ \{C_n\}$ называется полиномиальным, если существует полином, ограничивающий сверху количество элементов в схеме $ C_n$ для всех достаточно больших $ n$.

Альтернативно, алгоритм в неоднородной модели можно определить как семейство машин Тьюринга $ \{T_n\}$, где $ T_n$ работает на входных словах длины $ n$. Алгоритм $ \{T_n\}$ называется полиномиальным, если существует полином, ограничивающий сверху время работы машины $ T_n$ для всех достаточно больших $ n$. Это определение эквивалентно предыдущему.

Большинство определений и результатов теоретической криптографии могут быть сформулированы в обеих моделях вычислений. Всюду ниже мы будем подразумевать неоднородную модель. По-видимому, она ближе к потребностям криптографии: требуется, чтобы противник не мог найти эффективный алгоритм для каждого по отдельности достаточно большого $ n$, в то время как отсутствие у противника эффективных алгоритмов в однородной модели гарантирует, по сути, лишь высокую вычислительную сложность перехода от $ n$ к $ n+1$.


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 14.1.2 Односторонние функции в теории сложности Вверх: 14.1 Односторонние функции Назад: 14.1 Односторонние функции   Содержание   Предметный указатель


Проект осуществляется при поддержке:
Геологического факультета МГУ,
РФФИ
   
TopList Rambler's Top100