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

Например, вам хотелось бы подписать сообщение х = "Я обещаю заплатить Салли Ли 1О долларов", но вы не хотите, чтобы без вашего ведома Салли или кто-то третий могли создать сообщение, якобы подписанное вами. Для достижения этих целей вы выбираете ключ /с, простые сомножители которого известны только вам. Затем публикуете 1, например, на %еЬ-странице, так что любой может применить к вашему сообщению функцию 1».

Если вы хотите подписать упомянутое сообщение х и послать его Салли, вы вычисляете у = 6» '(х) и посылаете у Салли. Салли может взять |с, ваш »О бличный кч»оч, с вашей %еЬ-странипь» и с его помощью вычислить х = Яу). Таким образом, она знает, что вы действительно пообещали заплатить ей 1О долларов.

Если вы отказываетесь от факта отправки сообщения у, Салли может обосновать в супе, что только вам известна функция 1», и для нее или еще кого-то узнать эту функцию было бы "невозможно". Таким образом, только вы могли создать у. Данная система основана на вероятном, но не доказанном предположении, что произведение двух простых чисел очень трудно разложить на множители. Требования к сложности проверки простоты Оба описанных выше сценария считаются безопасными в том смысле, что разложение произведения двух простых чисел действительно требует экспоненциального времени. Теория сложности, представленная здесь и в главе 10, используется в изучении безопасности и криптографии следующими двумя путями.

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

Например, если нам нужны 64-битовые простые числа, достаточно проверить в среднем около 64 чисел, хотя в наихудшем случае понадобилось бы бесконечно много проверок. К сожалению, похоже, что гарантированно полиномиачьной проверки простоты не может быть, хотя и сушествует полиномиальный алгоритм типа Монте-Карло, как будет показано в разделе 11.5.4. 2. Безопасность шифрования, основанного на КБА-схеме, зависит от невозможности разложить произвольное целое число за полиномиальное (относительно числа битов в ключе) время, и в частности, от невозможности разложить целое, о котором известно, что оно — произведение двух больших простых чисел.

Мы были бы счастливы показать, что множество простых чисел образует ХР-полный язык, или даже что множество составных ХР-полно. Тогда полиномиальный алгоритм разложения доказывал бы, что 'Р=ЛР, поскольку приводил бы к полиномиальным по времени проверкам для обоих указанных языков. Увы, в разделе 11.5.5 будет показано, что языки как простых, так и составных чисел принадлежат ЛР. Они дополняют друг друга, поэтому, если бы какой-либо из них был ХР-полным, то выполнялось бы равенство ЛР = со-Л'Р, а его правильность весьма сомнительна. Кроме того, принадлежность множества простых чисел классу ЯР означает, что, если бы можно было показать ХР-полноту этого множества, то верным было бы равенство РР = ЛР, ко- торое также мачовероятно.

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

Модулярное сложение подчиняется об чным алгебраическим законам; оно коммутативно, ассоциативно и имеет 0 в качестве единицы. Вычитание остается обращением сложения, и модулярную разность х -у можно вычислить путем обычного вычитания и прибавления р, если результат меньше О. Обратным к х является -х, т.е. О-х, как и в обычной арифметике. Таким образом, — О = О, а если х м О, то -х — это то же, что р — х. Пример 11.21. Пусть р = 13. Тогда 3+ 5 = 8, а 7+ 10 = 4, поскольку в обычной арифметике 7+ 10 = 17, что не меньше !3. Отнимая !3, получаем правильное значение 4.

Значением — 5 глоба!о 13 будет 13 — 5, или 8. Разность 1! -4 тог!ц1о 13 равна 7, тогда как 4 — 11 — 6 !4 — 11 = -7, поэтому нужно прибавить 13 и получить 6). П Умножение по модулю р выполняется путем умножения обычных чисел и вычисления остатка от деления на р.

Умножение также удовлетворяет обычным алгебраическим законам; оно коммугативно и ассоциативно, единицей является 1, а нулем (аннигилятором) — О. Оно также дистрибугивно относительно сложения. Однако деление на ненулевые элементы сложнее, и даже существование обратных к целым по модулю р зависит от того, является ли р простым. В любом случае, если х есть одно из целых по модулю р, т.е. 0<х кр, то х ', или 17х — это такое число у (если существует), для которого ху= 1 щог!ц!о р. Пример 11.22. На рис.

11.9 показана таблица умножения для ненулевых целых чисел по модулю простого числа 7. Элемент в строке ! и столбце ! равен произведению 17 мог!ц!о 7. Отметим, что каждый ненулевой элемент имеет обратный; взаимно обратны 2 и 4, 3 и 5, а 1 и 6 обратны сами себе, т.е. 2 х 4, 3 х 5, 1 х 1 и 6 х 6 равны 1. Таким образом, можно делить на любой ненулевой элемент у, вычислив у ' и умножив на у '. Например, 374 = 3 х 4 = 3 х 2 = 6. Рис. !!.й Умножение помодулю 7 Сравним эту ситуацию с таблицей умножения по модулю 6. Во-первых, заметим, что обратные есть только у 3 и 5 !они обратны самим себе).

Другие числа обратных не имеют. Во-вторых, в таблице есть ненулевые элементы, произведение которых равно О, например, 2 и 3. Такое невозможно в обычной арифметике или в арифметике по модулю простого числа, П 11.б. СЛОЖНОСТЬ ПРОВЕРКИ ПРОСТОТЫ 613 Рис.

!!.!О. Умно>гение помодулю 6 Есть еще одно различие между умножением по модулю простого числа и по модулю составного, которое оказывается очень важным для проверки простоты. Порядок числа а по модулю р — это наименьшая положительная степень а, равная 1. Приведем без дока- зательства некоторые полезные сведения, связанные с порядком. ° Если р — простое, то а' ' = 1 щос!ц!о р.

Это утверждение называется теоремой Ферма. ° Порядок а по модулю простого р всегда является делителем р — 1. ° Если р — простое, то существует а, имеющее порядок р — 1 щодц!о р. Пример 11.23. Вернемся к таблице умножения по модулю 7 (см. рис, 11.9). Число 2 имеет порядок 3, поскольку 2'=4 и 2'= !. Порядком 3 является 6, так как 3'=2, 3'=6, 3' = 4, 3' = 5 и 3' = 1. Аналогично находим, что 4 имеет порядок 3, 6 — 2, а 1 — 1. П 11.5.3. Сложность вычислений в модулярной арифметике Перед тем как рассматривать применение модулярной арифметики к проверке простоты, нужно установить основные факты, связанные со временем выполнения существенных операций.

Предположим, нам нужно вычислять по модулю некоторого простого р, и двоичное представление р занимает и битов, т.е. само р близко к 2". Как всегда, время выполнения выражается в терминах и, длины входа, а не его "значения" р. Например, счет до р занимает время 0(2"), так что любое вычисление, включающее р шагов, будет ие полииомиальным по времени (как функции от и). На обычном компьютере или на многоленточной МТ можно сложить два числа по модулю р за время 0(п). Напомним, что нужно просто сложить два двоичных числа и, если результат не меньше р, вычесть р.

Аналогично, на компьютере или на машине Тьюринга можно умножить два числа за время 0(п ). После обычного умножения и получения результата длиной не более 2п бит, нужно поделить на р и взять остаток. Возведение числа х в степень сложнее, поскольку степень сама может быть зкспоненциальной относительно п.

Как мы увидим, большое значение будет иметь возведение Его не следует путать с "последней (большой, великой) теоремой Ферма", утверждающей несуществование целых решений уравнения х" е у" = я" прн и > 3. ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ 614 х в степень р — 1.

Поскольку р близко к 2", умножение х самого на себя р — 2 раз потребовало бы О(2") умножений, и даже если бы каждое умножение касалось лишь и-битовых чисел и выполнялось за время О(п'), общее время было бы О(п'2"), что не является полиномиальным относительно и. К счастью, существует следующий прием "рекурсивного удвоения", который позволяет вычислить х' ' (или любую другую степень до р) за время, полиномиальное относительно п.

1. Вычислим не более и степеней х, хт, х', х', ..., пока степень не превысит р — 1. Каждое значение является и-битовым числом, которое находится за время О(п ) путем возведения в квадрат предыдущего элемента последовательности, поэтому общее время равно О(п ). 2. Найдем двоичное представление р — 1, скажем, р — 1 = а„,...а,а,.

Можно записать р — ! = а, +2а, ~-4а2 ч- ... +2 'а„ь где каждое а, есть либо О, либо 1. Следовательно, р-1 2,+4 ~+..+2" м,, л =х" что представляет собой произведение тех степеней х~, для которых а, = 1. Поскольку все эти степени вычислены в п. 1 и являются и-битовыми, нх произведение (или произведение части из них) можно вычислить за время О(пз). Таким образом, все вычисление хк ' занимает время О(и'). 11.5.4.