Алгоритмы - построение и анализ (1021735), страница 201
Текст из файла (страница 201)
Увеличение значения а на 1 соответствует сдвигу по диагонали вниз и вправо. Таким образом, операции по модулю и можно выполнять непосредственно, а можно перейти к представлению, в котором вычисления производятся отдельно по модулям по Эти вычисления полностью эквивалентны, и есть возможность выбирать более удобный способ.
Упражнения 31.5-1. Найдите все решения уравнений х = 4(щос15) и х аь 5(шо611). 31.5-2. Найдите все целые числа х, которые при делении на 9, 8 и 7 дают остатки 1, 2 и 3 соответственно. 31.5-3. Докажите, что при выполнении условий теоремы 31.27, если йсб (а, и) = = 1, то (а ~ шобп) + ((а шодп1),(а 1шойп1),...,(а„щобпа)). 31.5-4. Докажите, что при выполнении условий теоремы 31.27 количество корней уравнения 7" (х) = 0 (шобп), где Г" — произвольный полипом, равно произведению количества корней уравнений г (х) = 0 (щойпт), г' (х) = : — 0 (шобла),..., г" (х) я— а 0 (щос1пь). Глава 31.
Теоретико-числовые алгоритмы 983 31.6 Степени элемента Рассматривать последовательность О ! 2 3 (31.29) степеней числа а по модулю и, гпе а е Е;„так же естественно, как и последовательность чисел, кратных а по модулю и. Индексация начинается от нуля; нулевой член последовательности равен ас гпос1 п = 1, а 1-й член — а' шос! п = 1. Ниже в качестве примера приведены степени чисел 3 и 2 по модулю 7: 0 1 2 3 4 5 6 7 8 9 10 11 3'шос17 1 3 2 6 4 5 1 3 2 6 4 5 2шос(7 1 2 4 ! 2 4 1 2 4 1 2 4 В этом разделе при помощи (а) будет обозначаться подгруппа группы Е„', сгенерированная элементом а путем повторного умножения, а огс1„(а) (порядок а по модулю и) будет обозначать порядок элемента а в группе Е„'.
Например, в группе Ет (2) = (1,2,4), а огс1т(2) = 3. Используя определение функции Эйлера ф(тс) в качестве размера группы Е„' (см. упражнение 31.3), преобразуем следствие 31.19 с использованием обозначений Е„', чтобы получить теорему Эйлера и сформулировать ее для частного случая группы Ер, где р — простое число, что даст нам теорему Ферма. Теорема 31.30 (Теорема Эйлера).
При любом целом значении тс ) 1 для всех аЕЕ;, ао("! =- 1(тос1п). И Теорема 31.31 (Теорема Ферма). Если р — простое число, то для всех а Е Е„' а" ~— : 1(пюс1р). ,ссоказансельсиюво. Согласно уравнению (31.20), для простых чисел р функция Эйлера равна ф (р) = р — 1. И Это следствие применимо к каждому элементу группы Ер за исключением нуля, поскольку 0 ф Ер. Однако для всех а е Ер, если р — простое число, справедливо соотношение а" = а (гпос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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
