Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 201
Текст из файла (страница 201)
Однако для всех а е Ер, если р — простое число, справедливо соотношение а" = а (гпос1р). Если огс1„(д) = !Е„'~, то каясдый элемент группы Е;, является степенью элемента д по модулю тс, и говорят, что д — нервообрвзный корень (рпппйче гооС), или генераясор (8епега!ог) группы Е;,. Например, 3 — первообразный юрень по модулю 7, но 2 таковым не является.
Если в группе Е„" существует первообразный юрень, то говорят, что она циклическая (сус!(с). Доказательство сформулированной ниже теоремы, доказанной Нивеном (Мчеп) и Цукерманом (Епс!сеппап) (231], опускается. Часть Ч!!. Избранные темы Теорема 31.32. Значения и > 1, для которых группа Е„' является циклической, равны 2, 4, р' и 2р' для всех простых чисел р > 2 и всех положительных целых показателях степени е. И Если д — первообразный юрень группы Е„*, а а — произвольный элемент этой группы, то существует такой элемент я, что д' = а(гпос1и). Это значение г называется дискретным логарифмаи (сйясгеге!ойаг!с!нп) или индексом (!лс)ех) элемента а по модулю и по основанию д, и обозначается как 1пс1„(а).
Теорема 31.33 (Теорема о дискретном логарифме). Если д — первообразный юрень группы в„', то уравнение д*: — дк (шос1и) справедливо тогда и только тогда, когда выполняется соотношение х = у (шос!ф (и)). Доказательство. Сначала предположим, что х = у (шос)ф (и)).
Тогда существует такое целое значение lс, для которого выполняется равенство х = у + Йф(и). Таким образом получаем д*=дз+ О(")( с)и)= — дя (дф(и)) (шос!и) : — д" 1" (шос)и) = = д" (гпос1и), где предпоследнее тождество следует из теоремы Эйлера. Теперь предположим, что д* =- дк (шос)и). Посюльку последовательность степеней д генерирует все элементы подгруппы (д), и !(д)~ = ф(и), то из следствия 31.18 вытекает, что последовательность степеней элемента д периодична с периодом ф(и). Таким образом, если д*: — дз (пюс1и), то справедливо соотношение х = у (шос!ф (и)).
и Вычисление дискретных логарифмов иногда позволяет упростить рассуждения, касающиеся модульных уравнений. Это иллюстрирует доказательство приведенной ниже теоремы. Теорема 31.34. Если р — нечетное простое число и е > 1, то уравнение х = 1(шос)р') (31.30) имеет всего два решения, а именно х = х1. Доказательство. Пусть и = р'. Из теоремы 31.32 следует, что группа Е„' имеет первообразный корень д. Уравнение (31.30) можно переписать следующим образом: ( )= ъз дыап в(х)) д!пй в(1) (шос)и) (31.31) Глава 31. Теоретико-числовые алгоритмы 985 С учетом того, что (пс1„д (1) = О, из теоремы 31.33 следует, что уравнение (31.31) эквивалентно следующему: (31.32) 2 ° шс1„(х) е— а О (пюс1ф (и)) .
Чтобы решить это уравнение относительно неизвестной величины !лс(„,д (х), воспользуемся методами, изложенными в разделе 31.4. Согласно уравнению (31.19), имеем ф(и) = ре(1 — Цр) = (р — 1) р' ~. Введяобозначениес( = йсс!(2,ф(и)) = = бес! (2, (р — 1) р' ') = 2 и заметив, что с! ~ О, согласно теореме 31.24 выясняем, что уравнение (31.32) имеет ровно д = 2 решений. Итак, уравнение (31.32) имеет ровно 2 решения, которые, как и ожидалось, равны х = 1 и х = -1. а Число х называется нетривиальным квадратным корнем нз 1 но модулю и (полспчса! зс!иаге гоос ог1, шос!и1о и), если справедливо уравнение хзта 1(шос(и), но х не эквивалентно ни одному из "тривиальных" квадратных корней по модулю и, — ни 1, ни — 1.
Например, 6 — нетривиальный квадратный корень 1 по модулю 35. Приведенное ниже следствие теоремы 31.34 будет использовано в разделе 31.8 при доказательстве корректности процедуры Миллера-Рабина (М!11ег-Ка!лл), в которой производится проверка простоты чисел. Следствие 31.35. Если существует нетривиальный квадратный корень 1 по мо- дулю и, то число и — составное. Доказательство.
Используем теорему, обратную теореме 31.34: если существует нетривиальный квадратный корень 1 по модулю и, то и не может быть нечетным простым числом или его степенью. Если хз = 1 (пюс12), то х = 1(пюс12), поэтому все квадратные корни 1 по модулю 2 тривиальны.
Таким образом, и не может быть простым. Наконец, чтобы существовал нетривиальный квадратный корень 1, и должно удовлетворять неравенству и > 1. Поэтому число и должно быть составным. в Возведение в степень путем последовательного возведения в квадрат В теоретико-числовых вычислениях часто встречается операция возведения одного числа в степень по модулю другого числа, известная под названием модульное возведение в степень (шос!и1аг ехролелйайоп). Другими словами, нам нужно найти эффективный способ вычисления величины аь пюс1 и, где а и 6— неотрицательные целые числа, а и — положительное целое число.
Операция модульного возведения в степень играет важную роль во многих подпрограммах, производящих проверку простоты чисел, а также в криптографической системе с открытым ключом КБА. Метод эффективного решения этой задачи, в котором 986 Часть Ч!1. Избранные темы используется бинарное представление числа Ь, называется методом повторного возведения в квадрат (гереасес1 зс(цапля). Пусть (Ьь Ьь ы..., Ьы Ьо) — бинарное представление числа Ь.
(длина бинарного представления равна 7с + 1, старший бит — Ьы младший — Ьо.) Приведенная ниже процедура вычисляет ас шос) и, где индекс с в ходе работы процедуры удваивается и увеличивается на 1, возрастая от 0 до Ь. МОИЛ.АК ЕХРОНННт1АтЮН(а, Ь, и) 1 с -0 2 с1 — 1 3 Пусть (Ьы Ьь ы..., Ьо) — бинарное представление числа Ь 4 1ог 1 — 1с дозгпто 0 5 с1о с~-2с 6 И вЂ” (с( с() шос) и 7 11'Ьс = 1 8 гйеп с — с+ 1 9 с( — (с1 ° а) пюс1 и 10 гегцгп с( Важной частью процедуры, объясняющей ее название ("повторное возведение в степень"), является возведение в квадрат в строке 6, которое производится в каждой итерации. В качестве иллюстрации работы алгоритма рассмотрим пример.
а = 7, Ь = 560 и и = 561. В этом случае алгоритм вычисляет последовательность величин по модулю 561, приведенную в табл. 31.5. Использованная в алгоритме последовательность показателей степени содержится в строке таблицы с меткой с. Значения переменной с на самом деле не нужны; они включены только для пояснения. В алгоритме поддерживается сформулированный ниже инвариант цикла, состоящий их двух частей.
Непосредственно перед каждой итерацией цикла Гог в строках 4-9 выполняются следующие условия. 1. Значение величины с совпадает с префиксной частью (Ьь, Ьь ы ..., Ьс+1) бинарного представления числа Ь. 2. с1 = а' пюс1 и. Таблица 31.5. Работа процедуры Мооиьлк Ехгонвнтсктсон по вычислению 7"' (пюд561) Глава 31. Теоретико-числовые алгоритмы 987 Используем этот инвариант цикла следующим образом. Инициализация. Изначально 1 = Ь, поэтому префикс (6|, Ьь и..., Ь;ч.1) пуст, что соответствует значению с = О. Кроме того, с1 = 1 = ао пюс1 и. Сохранение. Обозначим через с' и Н' значения переменных с и с1 в конце итерации цикла 1ог, которые в то же время являются значениями перед следующей итерацией. В каждой итерации эти значения обновляются с помощью операции с' — 2с (если Ь; = О) или с' — 2с+ 1 (если Ь, = 1), так что перед следующей итерацией значение с оказывается корректным.
Если Ь, = О„то с(~ = с(с шос1 = ( с)~ шос1 = азс по 1 = с шос1 Если же Ь; = 1„то с(' = сна шод и = (а ) а п1ос1 и = а~с+~ пюс1 и = ас тос1 и. В каждом случае перед очередной итерацией выполняется равенство с( = = ос шос1 и Завершение. В момент завершения 1 = — 1.
Таким образом, с = Ь, поскольку значение этой переменной равно префиксу (Ьь, Ьь ы..., Ьы Ьо) бинарного представления Ь. Следовательно, Н = ас шос1 и = аь пюс1 и. Если входные числа а, Ь и и являются ~3-битовыми, то общее количество необходимых арифметических операций равно О (13), а общее количество необходимых битовых операций — О (Дз). Упражнения 31.6-1. Составьте таблицу, в которой был бы показан порядок каждого элемента группы Е1 . Выберите наименьший первообразный корень д и вычислите таблицу значений 1пйы (ж) для всех х е Езп 31.6-2.
Разработайте алгоритм модульного возведения в степень, в котором биты числа Ь проверяются не слева направо, а справа налево. 31.6-3. Считая величину ф (и) известной, объясните, как с помощью процедуры Мори~ли Ехгоннмт~лт!ом вычислить величину а 1 шос1 и для любого аЕ 2ы.
31.7 Криптосистема с открытым ключом КЯА Криптографическую систему с открытым ключом можно использовать для шифровки сообщений, которыми обмениваются два партнера, чтобы посторонний, перехвативший зашифрованное сообщение, не смог его расшифровать. Кроме того, криптографическая система с открытым ключом позволяет партнерам Часть ЧП. Избранные темы 988 добавлять в конце электронных сообщений "цифровые подписи". Такая подпись представляет собой электронную версию подписи, поставленной от руки на бумажном документе. Любой без труда сможет ее проверить, но подделать не сможет никто. Кроме того, при изменении хотя бы одного бита в электронном сообщении оно теряет свою достоверность.
Таким образом, цифровая подпись не только позволяет идентифицировать автора сообщения, но и обеспечивает целостность его содержимого. Она является прекрасным инструментом для подписанных с помощью электронных средств деловых контрактов, электронных чеков, оформляемых в электронном виде заказов на поставку и других электронных документов, которые необходимо идентифицировать. Криптографическая система с открытым ключом КЯА основана на драматическом различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел. В разделе 3!.8 описана эффективная процедура поиска больших простых чисел, а в разделе 31.9 обсуждается проблема разложения больших целых чисел на множители. Криптографические системы с открытым ключом В криптографической системе с открытым ключом каждый участник располагает как открытым ключам (риЬ11с 1сеу), так и секретным ключам (зесге1 кеу).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
