Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
ж(р-1)/2 1 ±1 (modp). (4.4.7)
Проверка повторяется к = log2 р раз и завершается, когда ж^-1^2 равно — 1.
В соответствии с малой теоремой Ферма (теорема 6.10 в разделе 6.4), если число р является простым, то для всех чисел х < р выполняется следующее тождество:
хр~г = l(modp). (4.4.8)
Итак, если число р является простым, то функция Prime_Test(p) всегда возвращает ответ "ДА", т.е. выполняется равенство
Prob ja;^-1^2 ее ±l(modp) | р — простое числоj — 1.
С другой стороны, если число р является составным, то равенство (4.4.7), как правило, не будет выполняться. Как известно из теории групп (пример 5.2.3 и теорема 5.1 в разделе 5.2.1), если равенство (4.4.7) нарушается для какого-
Глава 4. Вычислительная сложность
145
Алгоритм 4.5. Вероятностная проверка простоты (алгоритм Монте-Карло) ВВОД: р: положительное целое число.
ВЫВОД: ДА, если число р является простым, и НЕТ — в противном случае.
Prime_Test(p)
1. Повторять log2p раз.
а) х ?и(1,р-1];
б) if gcd(a;,p) > 1 или х^'1^2 ? ± l(modp) return(HET); endofrepeat;
2. if (число в пункте 1.2 никогда не равно —1) геШгп(ДА).
3. ге1;шп(ДА).
нибудь числа х < р, для которого gcd(a;,p) = 1, то оно нарушается по крайней мере для половины чисел, удовлетворяющих неравенству х < р. Следовательно, для х € {/(IjP — 1]> такого что gcd(a;,p) = 1, выполняется неравенство:
Prob [ж^-1)/2 = ±l(modp) || р — составное число ^ 1/2. (4.4.9)
Таким образом, если из интервала (1,р — 1] к раз случайным образом извлекаются числа х, которые успешно проходят проверку (напомним, что в результате проверки хотя бы один раз вычисляется число —1), то вероятность того, что число р не является простым, не превышает 2~к. Здесь используется критерий "единогласного голосования": число р отклоняется, если среди log2 р проверок хотя бы одна оказалась неудачной. Обратите внимание на то, что критерий "единогласного голосования" отличается от критерия "голосования большинством", изученного нами в разделе 4.4.1 для задач с двусторонними оценками ошибок. Критерий "единогласного голосования" позволяет сделать вероятность противоречивости произвольно малой намного быстрее, чем критерий "голосования большинством".
Поскольку к = log2 р, для любого входного числа р выполняется неравенство
Prob [Prime_Test(p) = ДА || р — составное число] ^ 2_log2P.
В разделе 4.3 показано, что оценка сложности возведения в степень и вычисления наибольшего общего делителя для входного числа, состоящего из log2 р бит, имеет порядок OB((log2p)3)- Следовательно, временная сложность алгоритма PrimeTest(p) имеет порядок OB((logp)4).
Итак, мы показали, что язык PRIMES (множество всех простых чисел) принадлежит классу ^^(Монте-Карло).
Несмотря на то что этот факт не был опровергнут, в августе 2002 года три индийских специалиста в области компьютерных наук, Агравал (Agrawal), Кайал
146
Часть II. Математические основы
(Kayal) и Саена (Saena), изобрели детерминированный полиномальный алгоритм для проверки простоты числа [8]. Следовательно, фактически язык PRIMES принадлежит классу Р.
4.4.4 Подкласс "вероятно, высокочувствительных и всегда точных" алгоритмов
Подкласс РР(Лас-Вегас) класса РР обладает следующими свойствами. Для любого языка L е РР(Лас-Вегас) существует рандомизированный алгоритм А, такой что
РгоЬ[Л распознает Iе L \\ Iе L] ^ е, РгоЬ[Л распознает J е L \\ I ? L] = О,
где е — произвольная константа из интервала Q, 1). На самом деле константа в может принадлежать всему интервалу (0,1), поскольку, как и в случае односторонних оценок стойкости (раздел 4.4.3), в алгоритмах из класса (Лас-Вегас) нет необходимости применять критерий "голосования большинством".
Следует также отметить, что е ф 1. В противном случае подкласс РР(Лас-Вегас) вырождается в частный случай подкласса ZVV. Такие рандомизированные алгоритмы имеют одностороннюю оценку полноты. Иными словами, алгоритмы подкласса РР(Лас-Вегас) могут ошибочно отклонить предложение, которое на самом деле принадлежит языку. Однако если предложение распознано, ошибка исключена. Такие алгоритмы называются алгоритмами Лас-Вегаса (Las Vegas algorithms). Термин "Лас-Вегас" был впервые предложен в работе [16] и относится к алгоритмам, которые либо дают правильный ответ, либо не дают ответа вовсе.
Анализ, проведенный в разделе 4.4.1.1, показывает, что вероятность положительного ответа при использовании алгоритма Лас-Вегаса можно сделать сколь угодно близкой к единице, повторяя его применение. При этом алгоритм сохраняет полиномиальное время выполнения, а повторения должны быть независимыми друг от друга. В то время как алгоритмы Монте-Карло являются всегда высокочувствительными и не всегда точными, алгоритмы Лас-Вегаса являются, вероятно, высокочувствительными и всегда безошибочными ("probably fast and always correct").
С точки зрения вероятностей ошибок классы ZVV, РР(Монте-Карло) и РР(Лас-Вегас) связаны между собой следующим соотношением.
ZVV = РР(Монте-Карло) П РР(Лас-Вегас).
4.4.4.1 Пример алгоритма Лас-Вегаса
Пусть р — нечетное положительное целое число, а р— 1 = q\qi ¦ ¦ ¦ qk — полное разложение на простые множители числа р — 1 (некоторые простые множители
