Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Глава 4. Вычислительная сложность
147
могут повторяться). В главе 5 будет доказан следующий факт: (теорема 5.12 из раздела 5.4.4): число р является простым тогда и только тогда, когда существует положительное целое число д € [2,р — 1], такое что
op_1=" 1 modp, , " (4.4.10)
g(p-i)/Qi ?i modp для г = 1,2,..., А:.
Этот факт позволяет сформулировать алгоритм доказательства простоты числа. Введем нечетное число р, разложим число р— 1 на простые множители, а затем попытаемся найти число д, удовлетворяющее условию (4.4.10). Если такое число найдено, алгоритм выводит сообщение "ДА", и число р является простым. В противном случае алгоритм не принимает никакого решения, т.е. неизвестно, является ли число р простым или нет.
Алгоритм 4.6. Доказательство простоты числа (алгоритм Лас-Вегаса) ВВОД: р: нечетное положительное целое число;
4\i42i---iQk' все простые множители числар — 1.
ВЫВОД: ДА, если число р является простым,
и НЕПРИНЯТИЕРЕШЕНИЯ — в противном случае.
1. Извлекаем число д € и[2,р — 1];
2. for (г = 1, г + +, к) do
if gfr-1)/* ее lmodp output НЕПРИНЯТИЕ_РЕШЕНИЯ и terminate;
3. if gv~l ^l(modp) output НЕТ и terminate;
4. output ДА и terminate.
Поскольку к < log2(p — 1), алгоритм 4.6 имеет полиномиальное время выполнения, зависящее от размера числа р.
Из теоремы 5.12 (раздел 5.4.4) следует, что если алгоритм 4.6 выводит результат "ДА", то входное целое число р обязательно является простым — ошибка исключена. Если же алгоритм выводит ответ "НЕТ", ответ также является правильным, поскольку в противном случае не выполнялась бы малая теорема Ферма (4.4.8). Эти два свойства означают безошибочный алгоритм. Именно по этой причине он называется не "проверкой", а "доказательством" простоты числа.
Однако, если алгоритм 4.6 выводит ответ "НЕПРИНЯТИЕРЕШЕНИЯ", остается неизвестным, является ли число р простым или нет. Если на самом деле число р является простым, значит, алгоритм извлек неверное случайное число д. После изучения теоремы 5.12 из раздела 5.4.4 мы узнаем, что неверное число д не является первообразным корнем (primitive root).
148
Часть II. Математические основы
Итак, мы показали, что полнота алгоритма 4.6 имеет одностороннюю оценку, т.е. он относится к подклассу алгоритмов Лас-Вегаса. Этот алгоритм можно модив фицироватъ так, чтобы он не отказывался принимать решения, а искал другое слу-4 чайное число д. Модифицированный алгоритм остается алгоритмом Лас-Вегаса и становится "вероятно, высокочувствительным", поскольку не исключено, что oil будет постоянно извлекать тестовое число, не являющееся первообразным корнем. К счастью, для любого нечетного простого числа р мультипликативная группа по модулю р (определенная в главе 5) содержит большое количество первообразных корней, так что существует ненулевая вероятность, что при простом случайном выборе алгоритм извлечет из группы по модулю р искомое тестовое число. (В главе 5 будет дана оценка доли первообразных корней в мультипликативной группа по простому модулю.)
Алгоритмы Лас-Вегаса и Монте-Карло называются рандомизированными алгоритмами с односторонней ошибкой (randomized algorithms with one-sided error). Алгоритмы этого класса (напомним, что он включает в себя класс ZVV) действительно являются эффективными. Несмотря на то что они являются неде* терминированными, их временная сложность аналогична сложности алгоритмов из класса V.
4.4.4.2 Еще один пример алгоритма Лас-Вегаса: квантовая факторизация
Квантовый компьютер может разложить целое число на простые множители за время, которое полиномиально зависит от размера входного числа (т.е^ FACTORIZATION е QV). Этот алгоритм был предложен Шором (Shor) в рабо( те [267] (см. также [300]). Покажем, что квантовая факторизация Шора являете^ алгоритмом Лас-Вегаса.
Для того чтобы разложить на простые множители целое число N, из генеральной совокупности извлекается случайное целое число а. Используя идею Саймоне (Simon) об определении периода квантового состояния путем случайного выборе преобразования Фурье [276], квантовый алгоритм может найти период функции f(x) = ax(modN), т.е. наименьшее положительное целое число г, удовлетворяв* щее условию f(r) = 1. В главе 6 мы покажем, что для составного числа N доводы но большое количество целых чисел а, удовлетворяющих условию gcd(a, N) = 1, имеет четный период (называемый мультипликативным порядком элемента oj| т.е. г является четным числом.
Если период г оказался четным, то из неравенства аг12 ф ±l(mod N) следует, что число ar/2(modAQ является нетривиальным квадратным корнем единицы по модулю N. В разделе 6.6.2 (теорема 6.17) мы покажем, что число gcd(ar/2 ± 1, N\ является нетривиальным множителем числа N, т.е. алгоритм успешно разложив число на простые множители.
Глава 4. Вычислительная сложность
149
Если число г оказался нечетным или arl2 = ±l(modiV), то gcd(ar/2 ± 1, N) является тривиальным множителем числа N, т.е. единицей или числом N. Следовательно, алгоритм не дает ответа на поставленный вопрос. Однако для случайно выбранного целого числа а < N вероятность обнаружить неравенство ojl2 Ф Ф ±l(modiV) ограничена снизу константой е > 1/2. Значит, процедуру можно повторить, используя другое случайное число о. Анализируя алгоритм Шора (Shor), как показано в разделе 4.4.1.1, приходим к выводу, что он имеет полиномиальное время выполнения.
