Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
4.4.2 Подкласс "всегда высокочувствительных и всегда точных" алгоритмов
Подкласс класса VV называется подклассом ZVV (сокращение от Zero-sided Probabilistic Polynomial Time — полиномиальное вероятностное время с нулевой ошибкой), если оценки вероятностей (4.4.1) и (4.4.2) обладают следующими свойствами. Для любого языка L е ZVP существует рандомизированный алгоритм Л, при котором для любого предложения / выполняются условия
РгоЬ[Л распознает / € L \ I е L] = 1, РгоЬ[Л распознает / е L \ I ^ L] = 0.
Это означает, что случайная операция в рандомизированном алгоритме никогда не приводит к ошибкам. На первый взгляд класс ZW ничем не отличается от класса V. Однако существует класс задач, которые можно решить с помощью как детерминированных, так и рандомизированных алгоритмов за полиномиальное время. Причем, хотя рандомизированный алгоритм не делает никаких ошибок, его быстродействие намного выше, чем у детерминированного алгоритма. В свое время мы рассмотрим такой пример.
4.4.2.1 Примеры алгоритмов с нулевой ошибкой
Некоторые рандомизированные алгоритмы настолько естественны, что их детерминированные аналоги никогда не применяются. Например, чтобы взвесить предмет с помощью весов, пользователь должен передвигать гирьки на рычаге противовеса случайным образом. В этом случае он определит вес намного быстрее, чем детерминированным способом. Другим примером такого алгоритма является поиск телефонного номера в записной книжке.
Очевидно, что случайная операция, предусмотренная в алгоритме 4.4, не порождает ошибок. Следовательно, это действительно рандомизированный алгоритм с нулевой ошибкой. Если записная книжка состоит из N страниц, алгоритм 4.4 выполнит поиск за О (log N) шагов. Следует отметить, что детерминированный алгоритм найдет телефонный номер в записной книжке за O(N) шагов.
Глава 4. Вычислительная сложность
143
Алгоритм 4.4. Поиск телефонного номера в записной книжке (^РР-алгоритм) ВВОД: Name: имя человека.
Book: записная книжка. ВЫВОД: Искомый телефонный номер.
1. Повторять следующие операции, пока в записной книжке Book остается хотя бы одна страница.
{
а) Открыть записную книжку Book на произвольной странице.
б) Если искомое имя Name расположено до этой страницы, Book <— Предыдущие_страницы(5ооА:).
в) Иначе Book *— Следующие страницы.
}
2. геШгп(искомый телефонный номер).
Причина, объясняющая такое высокое быстродействие алгоритма 4.4, заключается в том, что все имена в записной книжке упорядочены по алфавиту. Заметим, что сама по себе сортировка также является ^Т^Р-алгоритмом: например, алгоритм быстрой сортировки [9] является рандомизированным. Он может упорядочить N элементов за N log N шагов, причем случайные операции не порождают никаких ошибок. В противоположность ему алгоритм сортировки методом пузырька является детерминированным. Он упорядочивает N элементов за N2 шагов [9].
Можно сказать, что подкласс ZVP содержит языки, которые можно распознать с помощью "всегда высокочувствительных и всегда точных" рандомизированных алгоритмов ("always fast and always correct" randomized algorithms).
4.4.3 Подкласс "всегда высокочувствительных и, вероятно, точных" алгоритмов
Подкласс класса W под названием W (Монте-Карло) обладает следующими характеристиками. Для любого языка L € ^^(Монте-Карло) существует рандомизированный алгоритм А, при котором для любого предложения J
Prob[A распознает J е L | J е L] = 1, РгоЬ[Л распознает J е L | J (fc L] ^ 5,
где 5 — произвольная константа из интервала (0, (Здесь термин "Монте-Карло" используется в качестве синонима слова "рандомизированный".) Однако, как ука-
144
Часть II. Математические основы
зано в разделе Л АЛ.2, поскольку алгоритмы с односторонними оценками ошибок не используют критерий "голосования большинством" для уменьшения вероятности ложного распознавания, число 6 на самом деле является произвольной константой из интервала (0,1).
Обратите внимание на то, что 6 ф 0. В противном случае рассматриваемый подкласс вырождается в частный случай подкласса ZVV. Рандомизированные алгоритмы с ограниченными вероятностями ошибок характеризуются односторонней оценкой вероятности ложного распознавания (one-sided error). Иначе говоря, такой алгоритм может распознать предложение, не относящееся к языку. Однако, если исходное предложение действительно принадлежит языку, оно всегда распознается. Этот подкласс алгоритмов называется алгоритмами Монте-Карло (Monte Carlo algorithms).
Как указано в разделе 4.4.1, повторяя метод Монте-Карло, можно сделать вероятность ошибки сколь угодно малой, причем итерационный алгоритм остается полиномиальным. Таким образом, можно утверждать, что алгоритм Монте-Карло всегда является высокочувствительным и, вероятно, точным ("always fast and probably correct").
Покажем теперь, что язык PRIMES (множество всех простых чисел) принадлежит подклассу ^^(Монте-Карло).
4.4.3.1 Пример алгоритма Монте-Карло
Со времен Ферма известно, что если число р является простым, а число х — взаимно простым с числом р, то жр-1 ее l(modp). Этот факт образует основу следующего метода Монте-Карло для проверки простоты числа [282]. Этот метод сводится к извлечению числа х € гу(1,р — l]cgcd(a?,p) = 1 и проверке
