Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений, страница 117

Так, из примера 11.14 следует, что снижение требуемой вероятности до 1/16 приведет к тому, что цепочка 00! окажется в языке рандомизированной МТ, описанной там. 11.4.7. Соотношение между Я:Р и лэгэР Между двумя определенными выше рандомизированными классами есть простое соотношение. Для того чтобы сформулировать теорему о нем, нужно сначала рассмотреть дополнения этих классов. Очевидно, если Т. принадлежит ЯРР, то Х тоже принадлежит гРР. Причина в.том, что если В допускается МТ М типа Лас-Вегас с полиномиально ограниченным ожидаемым временем, то Х допускается модификацией М, в которой допускание превращено в останов без допускания, и наоборот. 11.4.

КЛАССЫ ЯЗЫКОВ, ОСНОВАННЫЕ НА РАНДОМИЗАЦИИ 507 Однако замкнутость Т'Р относительно дополнения не очевидна, поскольку определение машины типа Монте-Карло трактует допускание и отвергание несимметрично. Таким образом, определим класс со-ЕР как множество языков 1., для которых Х принадлежит ЕР, т.е, этот класс образован дополнениями языков из ЯР. Теорема 11.17. ЯРР = ЕР() со-РР. Доказательство.

Сначала покажем, что Р.Р!) со-Т.Рс. ЕРР. Пусть ь принадлежит РР() со-РР, т.е. как (,, так и Х имеют МТ типа Монте-Карло с полиномиально ограниченным временем. Предположим, что р(п) — достаточно большой полипом, ограничивающий время работы обеих машин. Построим для Е машину Тьюринга М типа ЛасВегас следующим образом. 1. Запустим машину типа Монте-Карло для Т.; если она допускает, М допускает и останавливается. 2. Если машина для Е не допускает, запустим МТ типа Монте-Карло для Х .

Если эта МТ допускает, М останавливается без допускания. В противном случае возвращаемся к п. 1. Очевидно, М только допускает вход и, если и принадлежит Т„и только отвергает и; если эг не находится в Т.. Ожидаемое время работы в одном цикле (и. 1 и 2) — 2р(п). Вероятность того, что один цикл разрешит вопрос, не меньше 1/2. Если ч принадлежит Т„то п.

1 имеет 50;О шансов привести М к допусканию, а если не приналлежит — п. 2 имеет 5058 шансов привести М к отверганию. Таким образом, ожидаемое время работы Мне больше 1 1 1 2р(п) + — 2р(п) + — 2р(п) + — 2р(п) +... = 4р(п). 2 4 8 Рассмотрим обратное утверждение. Предположим, что 1, принадлежит ЯРР, и покажем, что Т, находится как в РР, так и в со-7'Р. Нам известно, что Е допускается МТ М~ типа Лас-Вегас, ожидаемое время работы которой — некоторый полином р(п). Построим для Е МТ М~ типа Монте-Карло следующим образом. М, имитирует 2р(п) шагов работы Мь Если М допускает в течение этого времени, то же делает и Мг, в противном случае она отвергает. Предположим, что вход ж длиной п не принадлежит 1.

Тогда М~ наверняка не допускает и; то же сделает и Мь Пусть вход и принадлежит 1,. М~ наверняка в конце концов допускает ж, но это может произойти как в пределах 2р(п) шагов, так и за их пределами. Однако мы утверждаем, что вероятность того, что М, допускает ч в пределах 2р(п) шагов, не меньше 1/2. Предположим, что эта вероятность является константой с < 1(2.

Тогда ожидаемое время работы М~ со входом зг не меньше (1 — с)2р(п), поскольку 1 — с является вероятностью того, что М~ нужно больше, чем 2р(п) времени. Но если с < 1!2, то 2(1 — с) > 1, и ожидаемое время работы М, со входом ж больше р(п). Получено противоречие с предположением, что Мг имеет ожидаемое время работы не больше р(п!. Это позволяет сделать вывод, что вероятность того, что Мг допускает, не меньше 1!2. Итак, Мэ является МТ типа Монте-Карло с полиномиально ограниченным временем, что доказывает принадлежность Е классу ЯР. 508 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ Для доказательства, что Е также находится в со-ЯР, используется, по существу, такая же конструкция, но с отрицанием выхода М„т.е. для того, чтобы допустить Х, М2 допускает, когда М~ отвергает в пределах времени 2р(п); в противном случае М, отвергает.

Теперь Мз является МТ типа Монте-Карло с полиномиально ограниченным временем для Х. П 11.4.8. Соотношения с классами Р и ЛХР Из теоремы ! !.!7 следует, что ЯРР< РР. Место этих классов между Р и ЛЕР опре- делают следующие простые теоремы. Теорема 11.18. 'Р с ЯРР. Доказательство. Любая детерминированная полиномиально ограниченная МТ является также полиномиально ограниченной МТ типа Лас-Вегас, не использующей возможности случайных выборов.

П Теорема 11.19. РР С ЛГР. Доказательство. Пусть для языка Е дана полиномиально ограниченная МТ Му типа Монте-Карло. Можно построить недетерминированную МТ М для Е с тем же ограничением времени, Когда М, рассматривает случайный бит в первый раз, М, недетерминированно выбирает оба возможных значения этого бита и записывает их на свою собственную ленту, имитирующую случайную ленту Мь М. допускает, когда допускает М„и не допускает в противном случае. Пусть ж принадлежит Е. Тогда, поскольку М~ имеет вероятность допускания ж не менее 50ОЛ, должна существовать последовательность битов на ее случайной ленте, ведущая к допусканию н. М, выберет эту последовательность битов среди прочих, и также допустит.

Таким образом, ж принадлежит ЦМ,). Однако если н не принадлежит Е, то ни одна последовательность случайных битов не приводит М, к допусканию, следовательно, нет и последовательности случайных выборов, приводящей к допусканню М,. Таким образом, ж не принадлежит ЦМз). П На рис. 11.8 представлены соотношения между введенными здесь и другими "близлежащими" классами. 11.5. Сложность проверки простоты В данном разделе представлена проблема проверки, является ли целое число простым. Вначале обсуждается, почему простые числа и проверка простоты составляют неотьемлемую часть в системах компьютерной безопасности. Далее показывается, что проблема простоты принадлежит как ЛГР, так и со-Л'Р.

Наконец, обсуждается рандомизированный алгоритм, показывающий, что эта проблема принадлежит также ЯР. 11.б. СЛОЖНОСТЬ ПРОВЕРКИ ПРОСТОТЫ 500 Рис. !!.8. Соотношение Яямл~ Я!Ри других классов 11.5.1. Важность проверки пустоты Целое число р называется простым, если его целыми положительными делителями являются только ! и само р. Если целое число не является простым, оно называется составным. Каждое составное число можно записать в виде произведения простых единственным образом с точностью до порядка сомножителей.

Пример 11.20. Первые пять простых чисел — это 2, 3, 5, 7, 11 и 17. Число 504 составное, а его разложение на простые имеет вид 2' х 3' х 7. Е3 Сугцествует множество способов, повышающих степень компьютерной безопасности и основанных на предположении, что разложение чисел, т.е. поиск их простых делителей, является трудной задачей. В частности, схемы, основанные на так называемых ЕБА- шифрах (Е.Е1иезг, А. Япаш1г, Е. Аг!1егпап — изобретатели этих шифров), используют 128-битовые целые, представляющие собой произведения двух простых, занимающих примерно по 64 бит.' Рассмотрим два сценария событий, в которых простые числа играют важную роль, ' В реально лействующих системах используются 5!2 — !024 и более битов для составных чисел и соответствующие количества для простых. См., например, А.1.

Мепехез, Р, С. мал оогс)зос, 8. А. Уапзгопе, !!ангг!лоо1 о! иррбед сгурголгарду, СЕС Ргем, !й97. — !урии. перев. б10 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ Шифрование с открытыми ключами Вы хотите купить книгу у продавца, подключенного к сети. Продавец запрашивает номер вашей кредитной карточки, но печатать номер в форме и посылать форму по телефонным линиям или через 1п»егпе» слишком рискованно, так как некий злоумышленник может подслушать линию или перехватить пакеты, идущие через 1пгегпес.

Чтобы предотвратить возможность прочитать номер вашей карточки, продавец посылает на ваш броузер ключ, возможно, 128-битовое произведение двух простых чисел, которые компьютер продавца сгенерировал специачьно для этого. Ваш броузер использует функциюу= Ях), которая берет ключ 1 и данные х, предназначенные для шифрования. Функцию 1; представляющую собой часть схемы КБА, могут знать даже потенциальные злоумышленники, но считается, что без знания разложения 1 обратную функцию1» ', для которой х = 1» 1у), невозможно вычислить за время, которое меньше экспоненциального по длине 1. Таким образом, даже если злоумышленник видит у и знает, как работает 1; он не сможет восстановить х (в данном случае номер кредитной карточки), не зная, как й раскладывается на множители. С другой стороны, продавец, зная разложение 1, сгенерированное им изначально„может легко применить |» ' и восстановить х по у.

Электронная подпись на основе публичных ключей Исходный сценарий, для которого были построены шифры КБА, был следующим. Вам хотелось бы "подписывать" электронную почту так, чтобы другие могли легко определить, что эта почта пришла именно от вас, и чтобы никто не мог подделать ваше имя на ней.