Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 219
Текст из файла (страница 219)
Этн вычисления полностью эквивалентны. Следствие 31.29 Если им из,...,пь попарно взаимно простые и и = п1пз иы то для любых целых чисел х и а х = а (пнк1 и;), 997 Глава ЗД Теоретико-числовые алюрлтмы Рис. 31.3. Иллюстрация китайской теоремы об остатках при нз = 5 и пз = 13. В этом примере сз = 26 и сз = 40. На пересечении строки 1 и столбца 7 показано значение а по модулю 65, такое, что а щоб 5 = з и а глоб 13 = 7.
Обратите внимание, что в ячейке на пересечении строки 0 и сюлбца 0 содержится значение О. Аналогично в ячейке на пересечении строки 4 и столбца 12 содержится 64 (эквивалент -1). Поскольку сэ = 26, смещение вниз вдоль столбца на одну строку приводит к увеличению значения о на 26. Аналогично сэ = 40 означает, что сдвиг вправо вдоль строки на один столбец приводит к увеличению значения а на 40.
Увеличение значения а на 1 соответствует сдвигу по диагонали вниз и вправо с переходом по доспакении границ нз нижней в верхнюю строку и из крайнего справа столбца в крайний слева. Упражнении 31.5.1 Найдите все решения уравнений х = 4 (пюс1 5) и х = 5 (шог( 11). 31.5.2 Найдите все целые числа х, которые при делении на 9, 8, 7 дают соответственно остатки 1, 2, 3. 31.5.3 Докажите, что при выполнении условий теоремы 31.27, если 8сс1(а, и) = 1, (а 1 шод п) <+ ((а11 шос) пг), (аз 1 тос1 пз),..., (аь шос( пь)) . 31.5.4 Докажите, что при выполнении условий теоремы 31.27 для произвольного поли- нома 1 количество корней уравнения 1(х) гя О (пюс1п) равно произведению количества корней каждого из уравнений 1(х) = — О (шод пг), 1(х) = О (шод из), ..., 1'(х) = О (гпос1 па).
31.6. Степени злементи Мы часто рассматриваем кратные данному элементу а по модулю и; столь же естественно рассматривать и последовательность степеней а по модулю п, где ц ~ ~о' 0 1 2 3 (31.33) по модулю и. Индексация начинается от нуля; нулевой член последовательности равен ао эпос( и = 1, а з-й член — а* шод и. Ниже в качестве примера приведены 998 Часть рц. Избранные анны степени чисел 3 по модулю 7. 1 0 1 2 3 4 5 6 7 8 9 10 11 3'пюс)7 1 3 2 6 4 5 1 3 2 6 4 5 А вот как выглядят степени 2 по модулю 7. 0 1 2 3 4 5 6 7 8 9 10 11 2'пюд7 ! 2 4 1 2 4 1 2 4 1 2 4 В этом разделе (а) будет обозначать подгруппу группы Е„', сгенерированную элементом а путем повторного умножения„а огг) „(а) (порядок а по модулю и) будет обозначать порядок элемента а в группе Ж'„.
Например, в группе Ет подгруппа (2) = (1, 2, 4), а огг(т(2) = 3. Используя определение функции Эйлера ф(и) как размера группы Ж„' (см. раздел 31.3), преобразуем следствие 31.19 с использованием обозначений Т,„', чтобы получить теорему Эйлера и сформулировать ее для частного случая группы Щ, где р — простое число, что даст нам теорему Ферма.
Теорема 31.30 (Теорема Эйлера) Для любого целого и > 1 а' ("1:— 1 (щос( и) для всех а Е Ж„' Теорема 31.31 (Теорема Ферма) Если р — простое число, то ая ' га 1 (гпос1 Р) дла всех а ~ Жр . Доказательство. Согласно (31.21), если р — простое число, ф(р) = р — 1. ° Теорема Ферма применима к каждому элементу Хр за исключением О, поскольку 0 1е Хр. Однако если р — простое, то аР ив з а (пюс1 р) для всех а е Хр.
Если оп1„(д) = ~Ж„'~, то каждый элемент группы Е„' является степенью д по модулю и и д представляет собой аервообразкмй корень (рпппйке гоо1), нлн геаератор К„'. Например, 3 является первообразным корнем по модулю 7, но 2 первообразным корнем по модулю 7 не является. Если в группе Т,„' имеется первообразный корень, то говорят, что она циклическая (сусйс), Доказательство сформулированной ниже теоремы, доказанной Нивеном 1гй(чеп) и Цукерманом (Хпскеппап) в (263), опущено.
Теорема 31.32 Значения и > 1, для которых группа Ж„* является циклической, представляют собой 2, 4, р' и 2р', для всех простых р > 2 и всех положительных целых е. ° Если д представляет собой первообразный корень группы Х*„, а а — произвольный элемент Т,„', то существует г, такое, что д' = а (пюс! и).
Это г называется Глава ЗЛ Теоретико-числовые алгоривииы 999 дискретныи логарифмом (Й1ясгеГе 1ойапйвп) или индексам (шйех) и по моду- лю и по основанию д; будем записывать это значение как шй„е(а). Теорема 31.33 (Теорема о дискретном логарифме) Если д является первообразным корнем Х„*, то равенство д* = д" (шой и) спра- ведливо тогда и толью тогда, югда выполняется х = у (гной ф(п)). + ь ф ( и ) ( ш о й и ) = д" (дф("1) (пюй и) = д" 1 (пкк1 и) га дя (гной и) .
(согласно теореме Эйлера) И обратно, предположим, что д* = д" (пюй и). Поскольку последовательность степеней д генерирует каждый элемент (д) и ~(д) ~ = ф(п), из следствия 31.18 вытекает, что последовательность степеней д периодична с периодом ф(п). Следовательно, если д* га дя (гной п), должно выполняться х ж у (гпой ф(п)). ° Теперь обратим внимание на квадратные корни из 1 по модулю простой степени. Приведенная ниже теорема окажется полезной в разделе 31.8 при разработке алгоритма для проверки простоты. Теорема 31.34 Если р представляет собой нечетное простое число и е > 1, то уравнение х = 1 (пюй р') (31.34) имеет только два решения, а именно — х = 1 и х = — 1. Доказательство. Уравнение (31.34) эквивалентно уравнению р' / (х — 1)(х + 1) .
Посюльку р > 2, может выполняться только одно из условий р ! (х — 1) и р ~ (х + 1), но не оба одновременно. (В противном случае согласно свойству (31.3) р должно быть делителем их разности (х + 1) — (х — 1) = 2.) Если р ( (х — 1), то 8сй(р', х — 1) = 1, и согласно следствию 31.5 должно выполняться р' ~ (х + 1), т.е. х = — 1 (той р').
Симметрично, если р 1 (х + 1), то 8сй(р', х + 1) = 1, и из следствия 31.5 вытекает, что р' ~ (х — 1)„так что х = 1 (шой р'). Следовательно, либо х = — 1 (гпой р'), либо х = 1 (тпой р'). Число х называется нетривиальным квадратным корнем 1 ио модулю и, если справедливо уравнение х = 1 (гпой и), но х не эквивалентно ни одному из "тривиальных" квадратных корней по модулю и, — ни 1, ни — 1. Например, Доказательство. Сначала предположим, что х г— а у (шой ф(п)). Тогда х = у + нф(п) для некоторого целого числа )с. Следовательно, гооо Часть УИ Избра»тые темы 6 — нетривиальный квадратный корень из 1 по модулю 35. Приведенное ниже следствие теоремы 31.34 будет использовано в разделе 31.8 при доказательстве корректности процедуры Миллера †Раби (М!Пег-КаЬш) для проверки простоты чисел.
Следствие 31.35 Если существует нетривиальный квадратный корень из 1 по модулю и, то число и составное. Доказательство. Будем проводить доказательство ст противного. Используем теорему, обратную теореме 31.34: если существует нетривиальный квадратный корень из 1 по модулю и, то и не может быть нечетным простым числом или его степенью. Если кз = 1 (шоб 2), то х = 1 (шос! 2), поэтому все квадратные корни 1 по модулю 2 тривиальны. Таким образом, и не может быть простым.
Наконец, чтобы существовал нетривиальный квадратный корень из 1, и должно удовлетворять неравенству и > 1. Поэтому число и должно быть составным. ° Возведение в степень путем многократного возведения в квадрат В теоретико-числовых вычислениях часто встречается операция возведения одного числа в степень по модулю другого числа, известная под названием модульное возведение в стелень (шобп!аг ехропепйайоп).
Другими словами, нам нужно найти эффективный способ вычисления величины аь шос) и, где а и Ь— неотрицательные целые числа, а и — положительное целое число. Операция модульного возведения в степень играет важную роль во многих подпрограммах, выполняющих проверку простоты чисел, а также в криптографической системе с открытым ключом КЗА.
Метод эффективного решения этой задачи, в котором используется бинарное представление числа Ь, называется методом многократного возведения в квадрат (гереа!ее) зс!палп8). Пусть (Ь», 6» и, .., Ьы Ьс) — бинарное представление числа Ь. (То есть бинарное представление имеет длину !с + 1 бит, Ь» — старший, а Ьо — младший биты представления.) Приведенная ниже процедура вычисляет а' шос! и, где с возрастает от 0 до Ь путем удвоения и приращения.
Мопиг.лк-Ехюнпмт!Атюн(а,Ь, и) ! с=О 2 0=1 3 Пусть (Ь»,6» п.,,,6о) — бинарное представление 6 4 !ог ! = )с йотгпго 0 5 с =2с б с( = (с( Н) гпос1 и 7 !ГЬ, ==1 8 с=с+1 9 с! = (Н а) пюс1 и 10 ге!игл д !00! Глава 3!. Теоретико-числовые олгоритмы Рис. 31.4.
Результаты работы процедуры Мооос ак-Ехгонантглтюн по вычислению о (пюс1 и), где о = 7, Ь = 660 = (1000110000) и и = 661. В таблице показаны значения после кткдой итерации цикла Гог. Окончательный результат равен единице Важной частью процедуры, объясняющей ее название ("многократное возведение в степень"), является возведение в квадрат в строке б, выполняемое в каждой итерации. В качестве иллюстрации работы алгоритма рассмотрим пример а = 7, Ь = 560 и п = 561. В этом случае алгоритм вычисляет последовательность величин по модулю 561, приведенную на рнс.
31.4. Полученная в алгоритме последовательность показателей степени содержится в строке с таблицы. В действительности алгоритм вполне может обойтись без переменной с; она добавлена для того, чтобы можно было сформулировать следующий состоязций из двух частей инвариант цикла. Непосредственно перед каждой итерацией цикла 1ог в строках 4 — 9 1. значение с совпадает с префиксом (Ьа, Ьа 1,..., Ьс.ьз) бинарного пред- ставления Ь; 2. с(= а' шос1 п. Используем этот инвариант цикла следующим образом. Инициализация. Изначально з = (с, так что префикс (Ьа, Ьа м..., Ь,.ьз) пуст, что соответствует с = О. Кроме того, сз = 1 = ао пюс1 п. Сохранение. Обозначим через с' и с(' значения с н с( в конце итерации цикла 1ог, а значит, значения перед началом следующей итерации.
Каждая итерация выполняет с' = 2с (если Ьс = 0) или с' = 2с+ 1 (если Ь, = 1), так что с будет иметь корректное значение перед следующей итерацией. Если Ьс = О, то сз' = с(з шос) и = (а')з тпос1 и = аз' аспас( и = а' шос) п. Если Ь = 1, то с(' = сзза шос) п = (а')за пюс1 п = аз''ьз шос( и = а' гпос1 п. В любом случае перед началом следующей итерации сз = а' гпос1 п.
Завершение. В момент завершения з = — 1. Таким образом, с = Ь, поскольку с имеет значение, равное префиксу (Ьь, Ьа 1,..., Ьо) бинарного представления Ь. Следовательно, с( = а' гпос1 п = аь пюс1 п. Если входные данные а, 6 и п представляют собой (3-битовые числа, то общее количество требуемых арифметических операций равно 0((з), а общее количество требуемых битовых операций равно Офз). Часть еп.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
