Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 199
Текст из файла (страница 199)
Аналогично, в группе Щ (1) = (1), (2) = (1,2,4), (3) = (1,2,3,4,5,6). Порядок (оп)ег) элемента а (в группе Я) обозначается как огг1 (а) и определяется как наименьшее положительное целое число г, для которого выполняется соотношение ай) = е. Теорема 31.17. Для любой конечной группы (Я, Ю) и любого ее элемента а Е Я порядок элемента равен размеру генерируемой им подгруппы, т.е. огс1 (а) = ~ (а) ~. Доказаиельсюаво. Пусть г = огг1 (а). Поскольку для й > 1 справедливы соотношения ай) = е и ай+") = а10 Ю а(") = а1"), то при г > 1 для некоторого у < в' выполняется равенство а10 = а0). Таким образом, после элемента ай) не появляется никаких новых элементов, так что (а) = (а0), а(з),..., а10 ) и 1(а)1 < г.
Докажем неравенство 1(а) ! > 1 методом "от противного". Предположим, что при некоторых 1 и ), удовлетворяющих неравенству 1 < 1 < 7' < 1, выполняется равенство а10 = а13). Тогда при )с > 0 ай+~) = аО+ь). Однако из этого следует, что а1'+О У)) = ай+О 3)) = е. Так мы приходим к противоречию, поскольку г+ (1 — ) ) < г, но 1 — наименьшее положительное значение такое, что ай) = е. Поэтому все элементы последовательности а("), а(з),..., ай) различны, и 1(а) ! > г. Таким образом, мы приходим к заключению, что огд (а) = ~(а) ~.
и Следствие 31.18. Последовательность а0), а(з),... является периодической с пе- риодом 1 = оп1 (а); т.е. а(0 = а0) тогда и только тогда, когда г = 7' (шогИ). Глава 31. Теоретико-числовые алгоритмы 975 С приведенным следствием согласуется определение а(о) как е, а аб) для всех целых 1 как аб "' ~ '1, где Ф = огс1 (а). Следствие 31.19. Если (Я, Ю) — конечная группа с единичным элементом е, то для всех а Е Я выполняется соотношение ай 1)=е. Доказавсельсвсво.
Из теоремы Лагранжа следует, что огс1 (а) / Д, так что ф/ =- : — 0 (шос11), где 1 = оп1 (а). Следовательно, абл<1 = а(о) = е. Упражнения 31.3-1. Составьте таблицу операций для групп (Е4, +4) и (Ез, в). Покажите, что этн группы изоморфны. Для этого обоснуйте взаимное однозначное соответствие сг между элементами этих групп, такое что а+ Ь= с (гпос(4) тогда и только тогда, когда о (а) . сс (Ь) = о (с) (тпос15). 31.3-2.
Докажите теорему 31.14. 31.3-3. Покажите, что если р — простое число, а е — положительное целое число, то справедливо соотношение ф (р') = р' ' (р — 1). 31.3-4. Покажите, что для любого числа п > 1 и для любого а е Е„' функция г'„: Е„' Е„', определяемая соотношением г" (х) = ах шос1 п, представляет собой перестановку Е;,.
31.3-5. Перечислите все подгруппы групп Ев и Е*,з. 31.4 Решение модульных линейных уравнений Теперь рассмотрим задачу о решении уравнений вида ах г— в Ь (тос1п), (31.21) где а > 0 и и > О. Эта задача имеет несколько приложений. Например, она используется как часть процедуры, предназначенной для поиска ключей для криптографической схемы В5А с открытым ключом, описанной в разделе 31.7. Предположим, что для заланных чисел а, Ь и и нужно найти все значения переменной х, которые удовлетворяют уравнению (31.21). Количество решений может быть равным нулю, единице, или быть больше единицы. Обозначим через (а) подгруппу группы Е„, сгенерированную элементом а.
Поскольку (а) = (а(з): х > 0) = (ах шос1 п: х > О), уравнение (31.21) имеет Часть Ч11. Избранные темы 976 решение тогда и только тогда, когда Ь е (а). В теореме Лагранжа (теорема 31.15) утверждается, что величина ~(а) ~ должна быть делителем числа п.
Сформулированная ниже теорема дает точную характеристику подгруппы (а). Теорема 31.20. Для всех положительных целых чисел а и п из соотношения Н = бей(а,п) следует, что (а) = (с1) = (О,Ы,2с(,..., ((и/с1) — 1)<Ц (31.22) в с„, так что )(а) / = и/й. Доказательство. Для начала покажем, что Н Е (а). Напомним, что процедура Ехтнмпнп Еоп.пз(а, п) выдает целые числа х' и у', удовлетворяющие уравнению ах'+ пу' = Ы. Таким образом, выполняется соотношение ах' = д (пзос1п), так что и е (а). Поскольку Ы Е (а), можно сделать вывод, что подгруппе (а) принадлежат все числа, кратные Н, так как любое число, кратное числу, кратному а, является кратным числу а. Таким образом, подгруппа (а) содержит все элементы множества (О, с(, 2Н,..., ((п/ф — 1) с1), т е.
(Н) С (а). Теперь покажем, что (а) С (с1). Если т б (а), то для некоторого целого числа х выполняется равенство т = ах пюй п, так что т = ах + пу для некоторого целого у. Однако И ! а и И ( п, поэтому Ы ! т согласно уравнению (3!.4). Таким образом, т е (д). Обьединяя эти результаты, получаем (а) = (с1).
Чтобы убедиться, что ~(а) ~ = = и/г1, заметим, что между числами 0 и и — 1 включительно, имеется ровно п/Й чисел, кратных И. И Следствие 31.21. Уравнение ах=Ь (шодп) разрешимо относительно неизвестной величины х тогда и только тогда, когда бей (а, и) ~ 6.
Ю Следствие 31.22. Уравнение ах = — 6 (шог)п) либо имеет д = ась (а, п) различных решений по модулю п, либо не имеет решений вовсе. Доказательство. Если уравнение ах = Ь (шойи) имеет решение, то 6 Е (а). Согласно теореме 31.17, огс1 (а) = ~(а) ~, поэтому из следствия 31.18 и теоремы 31.20 вытекает, что последовательность а1 шод п при г = 0,1,...,п — 1 периодична с периодом ((а)! = и/с(. Если 6 е (а) то Ь появляется в последовательности аг шоб и (1 = О, 1,..., и — 1) ровно д раз, поскольку при возрастании индекса 1 от 0 до п — 1 блок элементов подгруппы (а) длиной п/д.
повторяется ровно И раз. Индексы х тех Ы позиций, для которых ах шой п = Ь, и являются решениями уравнения ах ив з Ь (шос1п). И Глава 31. Теоретико-числовые алгоритмы 977 Теорема 31.23. Пусть с1 = ясс1 (а, п), и предположим, что равенство И = ах'+ + Ьу' выполняется для некоторых значений х' и у' (эти значения можно получить, например, с помощью процедуры ЕХтнчРЕо Еисми). Если с1 ~ Ь, то одно из решений уравнения ах = Ь (пюс1п) — значение хо = х' (Ь/с1) шос1 и.
Даказалсельслсво. Справедлива цепочка равенств ахо = ах' (Ь/с1) (шос1п) — = с1 (Ь/с1) (пюс1п) — = Ь (тос1 п), где второе тождество следует из того, что ах' = с1(пюс1п), так что хо является решением уравнения ах = Ь (пюс1п). Теорема 31.24. Предположим, что уравнение ах аа Ь(пюс1п) имеет решение (т.е. с1 ! Ь, где с1 = ясс1 (а, и)), и что хо — некоторое решение этого уравнения. Тогда это уравнение имеет ровно И различных решений по модулю и, и эти решения выражаются соотношением х; = хо + 1 (и/с1) при 1 = О, 1,..., с1 — 1.
Доказательство. Поскольку п/с1 ) О, и О < г(п/с1) < п при 1 = 0,1,..., с1 — 1, все значениЯ последовательности хо,хы..., х4 ~ по модУлю п Различны. Поскольку хо — решение уравнения ах = Ь(шос)п), справедливо соотношение ахо шос1 п = Ь. Таким образом, при 1 = О, 1,..., с1 — 1 выполняются соотношения ах, пюс1 и = а (хо + 1п/с1) шос1 п = = (ахо + азп/с1) шос1 и = = ахо шос1 и = =Ь, где третье равенство следует из того, что с1 ~ а, поэтому все х; тоже являются решениями данного уравнения.
В соответствии со следствием 31.22, всего имеется с1 различных решений, так что все рассматриваемые значения хо,хы..., х4 ~ должны быть таковыми. Теперь у нас имеется математический аппарат, необходимый для решения уравнения вида ах = Ь (шос1п), а ниже приведен алгоритм, который выводит все его решения. На вход алгоритма подаются произвольные положительные целые числа а и п, и произвольное целое число Ь. Мооя.лк ?.ЕчеАк ЕОилтюм Босзсек(а, Ь, и) 1 (сз, х', у') — ЕХТЕХОЕ0 Ес3СЕ10(а, п) 2 11с1! Ь 3 гйеп хо — х'(Ь/сК) пюс1 п 4 1ог1 ~ — О го И вЂ” 1 5 с1о рйпс (хо + з(п/с1)) шос) п 6 е!зе рппс "Решений нет" 978 Часть Чпй Избранные темы В качестве примера работы этой процедуры рассмотрим уравнение 14х = = 30(шог1100) (здесь а = 14, Ь = 30 и п = 100).
Взывав в строке 1 процедуру Ехткыоко Еосьш, получаем набор выходных данных (Ы,х,у) = (2,-7,1). Поскольку 2 ) 30, выполняются строки 3-5. В строке 3 вычисляется значение хо = (-7) (15) шос1 100 = 95. В цикле в строках 4-5 выводятся два решения уравнения, равные 95 и 45. Опишем работу процедуры Моогл.лк Ьпчелк ЕОилтюы Боьчкк. В строке 1 вычисляется величина г1 = бсг1 (а, п), а также величины х' и у', такие что Н = ах'+ + пу', что свидетельствует о том, что х' удовлетворяет исходному уравнению.
Если 4 не является делителем числа Ь, то уравнение решений не имеет согласно следствию 31.21. В строке 2 проверяется, делится ли Ь на д; если нет, то в строке 6 выводится сообщение об отсутствии решений заданного уравнения. В противном случае в строке 3, в соответствии с теоремой 31.23, вычисляется решение ха уравнения ах аз Ь (шос1п). Если найдено одно решение, то, согласно теореме 31.24, остальные г1 — 1 решений можно получить путем добавления величин, кратных (п7'й) по модулю и. Это и делается в цикле 1ог в строках 4-5, где с шагом (п(й) по модулю и выводятся все Н решений, начиная с хо. В процедуре Мооиык Ьпчклк ЕОилтюы Яоьчек выполняется 0(18п + + ясг1(а, и)) арифметических операций, поскольку в процедуре Ехтеыою Еисгзп выполняется 0 (18 и) арифметических операций, и при каждой итерации цикла Гог в строках 4-5 производится фиксированное количество арифметических операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
