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

Рандомизированная подиномиальная проверка простоты Теперь обсудим, как применить рандомизированные вычисления для поиска больших простых чисел. Точнее, покажем, что язык составных чисел принадлежит ЯР. Метод, который в действительности используется для генерации и-битовых простых чисел, состоит в том, что случайно выбирается и-битовое число и много раз, скажем, 50, применяется алгоритм типа Монте-Карло для распознавания составных чисел. Если некоторая проверка показывает, что число составное, то оно точно не простое.

Если все 50 проверок не могут сказать, что оно составное, то вероятность того, что оно действительно составное, не больше 2 '~. Таким образом, можно довольно уверенно сказать, что число простое, и этим обосновать безопасность наших операций. Полный алгоритм здесь не приводится, но обсуждается идея, имеющая очень мало исключений. Напомним, что теорема Ферма гласит: если р — простое, то х' ' шодп!ар для любого х равно ! . Верно и то, что если р — составное, и существует х, для которого х' ' шог!п1о р не равно 1, то не менее половины чисел у от 1 до р — 1 имеют у' ' и 1.

Таким образом, используем следующий алгоритм типа Монте-Карло для составных чисел. 1. Выберем случайно х из диапазона от 1 до р — 1. 11.5. СЛОЖНОСТЬ ПРОВЕРКИ ПРОСТОТЫ 515 2, Вычислим х' щодц!ор. Заметим, что если р есть и-битовое число, то это вычислер-1 ние занимает время О(п') (см. конец раздела 11.5.3). 3. Если х' и 1 щодц!о р, то допустим вход, т.е.

х — составное. В противном случае ос- 1 тановимся без допускання. Если р является простым, то х1 ' = 1, так что мы всегда останавливаемся без допускания; это одна часть условий типа Монте-Карло — если вход не принадлежит языку, то никогда не допускается. Почти для всех составных чисел не менее половины х будут иметь х'" м 1, поэтому у нас есть не менее 50ОА шансов допускания при любом запуске р-1 этого алгоритма, т,е. верно другое условие, налагаемое на алгоритмы типа Монте-Карло. Представленные рассуждения были бы демонстрацией того, что проблема составных чисел принадлежит РР, если бы не существование небольшого количества составных чисел с, дающих х' ' = 1 щодц1о с для большинства х от 1 до с — 1, в частности, для к, взаимно простых с с.

Эти числа, называемые числами Кармайкла (Сагт1сйае7), требуют проведения еще одной, более сложной, проверки (она здесь не описывается), чтобы убедиться, что они составные. Наименьшим числом Кармайкла является 561, т.е. можно показать, что х"~= 1 шодц1о 561 для всех х, которые не делятся на 3, 11 или 17, хотя 561 = 3 х 11 х 17, очевидно, составное. Итак, утверждается, но без полного доказательст- ва, следующее.

Теорема 11.24. Множество составных чисел принадлежит ЯР. Е) Можно ли разложить на множители за случайное полиномиальное время7 Отметим, что алгоритм из раздела 11.5.4 может сказать, что число является составным, но не говорит, как составное число разложить на множители. Есть основания 11олагать, что не существует способа разложения, даже с использованием рандомизации, которому было бы достаточно полиномиального или хотя бы ожидаемого полиномиального времени. Если бы это предположение было неправильным, то приложения, описанные в разделе ! 1.5.1, были бы небезопасными и их нельзя было использовать. 11.5.5. Недетерминированные проверки простоты Здесь обсуждается еще один важный и интересный результат, связанный с проверкой простоты, — язык простых чисел находится в Л'Р П со-ЛР.

Следовательно, язык составных чисел, представляющий собой дополнение языка простых, также принадлежит Л'РП со-ЛР. Отсюда следует, что вероятность ХР-полноты языков простых и составных чисел ничтожна, поскольку, если бы это было так, истинным стало бы совершенно невероятное равенство ЛР = со-ЛР. 61б ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ Одна часть указанного утверждения проста — язык составных чисел принадлежит гу T, поэтому язык простых чисел находится в со-Л"Р. Докажем это утверждение.

Теорема 11.25. Множество составных чисел принадлежит ЛФ. Доказательство. Недетерминированный полиномиальный алгоритм распознавания составных чисел имеет следующий вид. 1. Имея данное н-битовое число р, угадаем сомножитель); состоящий не более, чем из н битов (г = 1 илиу'= р, естественно, не рассматриваются).

2. Разделим р на7 и проверим, что остаток равен О. Допускаем, если так. Данная часть детерминирована и может быть выполнена за время 0(п ) на многоленточной МТ. Если р — составное, то оно должно иметь хотя бы один сомножительу, не равный 1 и р. НМТ„угадывающая все возможные числа, содержание не более и битов, по одной из веток угадает 1: Эта ветка ведет к допусканию. Наоборот, допускание НМТ означает, что найден делитель числа р, не равный ! и р.

Таким образом, язык описанной НМТ содержит все составные числа, и ничего более. С) Распознавание простых чисел с помощью НМТ сложнее. Можно было угадать причину (делитель) того, что число не является простым, но как проверить корректность предположения, что число действительно является простым? Недетерминнрованный полиномиальный алгоритм основан на том факте (утверждаемом, но не доказанном), что, если р — простое, то сушествует число х между 1 и р — 1, имеющее порядок р — 1.

В частности, в примере 11.23 отмечалось, что при простом р = 7 числа 3 и 5 имеют порядок 6. Можно легко угадать число х, используя недетерминированность МТ, но совершенно неясно, как проверить, что х имеет порядок р — 1. Причина в том, что, если определение порядка применяется непосредственно, то нужно проверить, что ни одно из г р-г чисел х, х, ..., хв не равно 1. Но такая проверка требует времени не менее 2", если р — л-битовое число.

Лучшая стратегия — использовать еше один факт, который утверждался, но не был доказан, а именно: порядок х по модулю простого р является делителем р — 1. Таким образом, если бы нам были известны простые делители р — 1'о, было бы достаточно проверить, что х м 1 для каждого простого сомножителя г? числа р — 1. Если бы ни одна из (г-шч этих степеней х не равнялась 1, то порядком х было бы р — !. Число таких проверок есть 0(н), поэтому все их можно выполнить с помошью полиномиального алгоритма. Конечно, разложить р — 1 на простые сомножители нелегко, на можно угадангь их, и проверить, что а) их произведение действительно равно р — 1; и Заметим, что, если р — простое, то р — ! не может быль простым, кроме как в тривиальном случае р = 3.

Причина в том, что все простые, кроме 2, нечетны. 11.5. СЛОЖНОСТЬ ПРОВЕРКИ ПРОСТОТЫ б) каждый нз них является простым, используя данный недетерминированный полиномиальный алгоритм рекурсивно. Детали алгоритма и доказательство того, что он является недетерминированным полиномиальным, приводятся в следующей теореме. Теорема 11.26. Множество простых чисел принадлежит ЛР. Доказательство. Пусть р — и-битовое число. Если и не больше 2 (т.е.

р — это 1, 2 или 3), то отвечаем сразу: 2 и 3 — простые, 1 — нет. В противном случае выполним следующее. 1. Угадаем список сомножителей (д~, дь ..., д~), двоичные представления которых вместе занимают не более 2п битов, и ни одно из ннх не имеет более и — 1 битов, Одно и то же простое число может появляться несколько раз, поскольку р — 1 может иметь сомножитель, возводимый в степень больше 1. Например, если р =!3, то простые сомножители р — 1 = 12 образуют список (2, 2, 3). Данная часть алгоритма недетерминирована, но каждая ветвь требует времени 0(и).

2. Перемножим все сомножители д, и проверим, равно ли их произведение р — 1. Эта часть требует времени не более 0(и') и является детерминированной, Если произведение сомножителей равно р — 1, то рекурсивно проверим, является ли каждый из них простым, используя данный алгоритм.

Если не все д просты, угадаем значение х и проверим неравенство хе"'~' ~ 1 для каждого из ц. Эта проверка обеспечивает, что х имеет порядок р — 1 тог(п1ор, поскольку, если бы это было не так, то его порядок должен был бы делиться хотя бы на одно из (р — 1)/ц, но мы только что установили, что он не делится. В подтверждение заметим, что любое х при возведении в степень его порядка должно равняться 1. Возведения в степень можно выполнить эффективным методом, описанным в разделе 11.5.3.

Таким образом, нужно выполнить не более А возведений в степень, что не больше и, и каждое можно выполнить за время 0(п'), что дает общее время О(п') для каждого шага. Наконец, нужно проверить, что приведенный недетерминированный алгоритм полиномиален. Каждый шаг, за исключением рекурсивного шага 3, требует времени 0(и) вдоль любой недетерминированной ветви. Поскольку рекурсия нелинейна, рекурсивные вызовы можно изобразить в виде дерева (рис. 11.11). В корне находится и-битовое р, проверяемое на простоту. Сыновьями корня являются ц, — угадываемые сомножители р — 1, которые также нужно проверить на простоту. Под каждым д, находятся угадываемые сомножители гу, — 1, которые также нужно проверить, и так далее, пока не дойдем до чисел, состоящих не более, чем нз 2 бит — листьев дерева. Произведение сыновей любого узла меньше значения в самом этом узле, поэтому произведение значений в узлах любого уровня не более р.

Время работы, выполняемой для узла со значением 1, исключая работу в рекурсивных вызовах, оценивается 818 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ как а(!ойзз) длЯ некотоРой константы а, посколькУ это вРемЯ пРЯмо пРопоРционально четвертой степени количества битов, необходимых для двоичного представ- ления значения з, Уровень корня Уровень 1 Я Л Уровень 2 Л Рис. ! !.

! !. Рекурсивные вызовы, совершаемые алгоритмом из теоремы ! !2б, образуют дерево высотой и шириной не более п Таким образом, чтобы получить верхнюю оценку времени работы на любом уровне, ограничим сверху сумму,"~ а(1о8,(! ))', учитывая, что произведение !нз... не превосхо- 3 дит р. Если з, = р, и других з, нет, то сумма равна а(!озер)', т.е. не превосходит али, поскольку л — число битов двоичного представления р, а !ойзр не более ж Итак, время работы на каждом уровне глубины не превышает 0(л'). Так как у дерева не более л уровней, для любой ветви недетерминированной проверки, является ли р простым, достаточно 0(и ).

С3 Теперь ясно, что языки и простых, и составных чисел находятся в ЯР. Если бы один из них был )9р-полным, то по теореме ! 1.2 это доказывало бы, что )з!Р = со-,Л!Р. 11.5.6. Упражнения к разделу 11.5 115.1. Вычислите следуюшие значения по модулю 13: а) 1 ! + 9; 6) (е) 9 — !1; в) 5х8; г) (к) 5 18; д) 5. 11.5.2. В разделе 1!.5.4 утверждалось, что х'в' = 1 шобп!о 561 лля большинства значений х между 1 и 560.

Выберите какие-нибудь значения х и проверьте это равенство. Конечно, сначала выразите 560 в двоичном виде, а затем вычислите х для соответствуюших значений ), избегая 559 умножений (см. раздел ! 1.5.3). 11.6. СЛОЖНОСТЬ ПРОВЕРКИ ПРОСТОТЫ 619 11.5.3. Целое число х между 1 и р — 1 называется квадратичным вычетом по модулю р, если сушествует целое у между 1 и р — 1, для которого у = х. а) (в) Укажите квадратичные вычеты по модулю 7.