Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 217
Текст из файла (страница 217)
Приведенная далее теорема служит полезным инструментом распознавания подгрупп. Теорема 31.14 (Непустое замкнутое подмножество конечной группы является подгруппой) Если (Я, Е) является конечной группой, а У вЂ” любое непустое подмножество Я, такое, что и Ю Ь Е У для всех а, Ь 6 У, то (У, Ю) является подгруппой (Я. Ю). Например, множество (0,2,4,6) образует подгруппу группы е.а, поскольку оно непустое и замкнуто относительно операции + (т.е. оно замкнуто относительно операции +а). Сформулированная ниже теорема крайне полезна для оценки размера подгруппы; доказательство этой теоремы опущено.
Теорема 31.15 (Теорема Лагранжа) Если (Я, Ю) представляет собой конечную группу и (У,Е) является подгруп- пой (о, ®), то !У~ является делителем ~51 Подгруппу У группы Я называют истинной (ргорег) подгруппой, если У ф Я. Приведенное ниже следствие из этой теоремы окажется полезным при анализе теста простых чисел Миллера — Рабина (М111ег-КаЬ(п), описанного в разделе 31.8.
Следствие 31. 16 Если У является истинной подгруппой конечной группы Я, то ~У~ ( ~Я! /2. ° Подгруппы, сгенерированные элементом группы Теорема 31.14 предоставляет интересный способ, позволяющий сформировать подгруппу конечной группы (Я, Ю). Для этого следует выбрать какой-нибудь элемент группы а и выделить все элементы, которые можно сгенерировать с помо- Доказательство. Доказать эту теорему читателю предлагается самостоятельно в упр. 3! .3.3.
9(В Часть УИ. Иэбраиные теан щью элемента а и групповой операции. Точнее говоря, определим элемент а(") для Й > 1 как "=Щ = е е "е Например, если взять а = 2 из группы г.а, то последовательность а(1),а(з), а(з),... имеет вид 2,4,0,2,4,0,2,4,0,.... В группе г'„мы имеем а(") = ка пюс) и, а в группе К„' — аоо = аь пюб и. Определим подгруппу, сгенерированную элементом а (обозначается как (а) или ((а), Ю)) следующим образом: (а) = (а( ): Й > Ц . Будем говорить, что а генерирует подгруппу (а) или что а является генераторам (а).
Поскольку множество Я конечно, (а) является конечным подмножеством Я, возможно, включающим все элементы Я. Так как из ассоциативности Ю вытекает о(з) щ о(1) о(а.~.г) (а) замкнуто, а значит, согласно теореме 31.14 (а) является подгруппой Я. На- пример, в Жа мы имеем (о) = (о), (1) = (0,1,2,3,4,5), (2) = (0,2,4) . Аналогично в Щ мы имеем (1) = (1), (2) = (1,2,4), (3) = (1,2,3,4,5,6) Порядок (огбег) элемента а (в ~рупие Я), записываемый как огс)(а), определяется как наименьшее положительное целое число Г, такое, что а(') = е. Теореме 31.17 Для любой конечной группы (Я, (В) и любого ее элемента а е Я порядок элемента а равен размеру генерируемой им подгруппы, т.е.
огс1(а) = ~(а) ~. Доказательство. Пусть ( = огг)(о). Поскольку а(') = е и а('+~) = а(') Э а(~) = а(") для Й > 1, при 4 > ( для некоторого з < 1 выполняется равенство а(0 = ао). Таким образом, при генерации элементом а после элемента а(') не появляется никаких новых элементов. Таким образом, (а) = (а('), а(з),..., а(')) и )(а) ~ < (. Чтобы показать, что )(а)~ > Г, покажем, что все элементы последовательности 989 Глотг 31.
Теоретико-числовые алгоритмы ай), а(з),..., а(') различны. Будем действовать методом от противного. Предположим, что при некоторых 1 и 3, удовлетворяющих неравенству 1 < 1 < 3 < Г, выполняется равенство аб) = а11), Тогда при и > О имеем абв ь) = ай+~). Однако из этого следует, что ар ьр 1)) = а114 О 1)) = е. Так мы приходим к противоречию, поскольку 1+ (à — 3) < г, но à — наименьшее положительное значение, такое, что ар) = е. Поэтому все элементы последовательности ац), а(~),..., ар) различны, и )(а) ~ ) г.
Таким образом, мы приходим к заключению, что огс1(а) = ) (а) !. ° Следствие 31.18 Последовательность ац), а(з),... периодична с периодом г = огй(а); т.е. аб) = аб) тогда и только тогда, когда 1 з— а 3' (шос( г). С приведенным следствием согласуется определение абй как е, а а(') для всех ЦЕЛЫХ 1 — КаК аб го"-о '), ГдЕ Г = ОГС1(а). Следствие 31.19 Если (Я,Ю) — конечная группа с единичным элементом е, то для всех а Е Я выполняется соотношение а1) )) = е. Доказагюельсгювв.
Из теоремы Лагранжа (теорема 31.15) следует, что оп1(а) ! ф/, так что ф/ = О (1пос1 1), где Г = огс1(а). Следовательно, аблО = а(0) е Упражнения 31З.1 Составьте таблицы операций для групп (44, +4) и (Цк.ь), Покажите, что эти группы изоморфны. Для этого продемонстрируйте взаимное однозначное соответствие а между элементами этих групп, такое, что а + б: — с (шос) 4) тогда и только тогда, когда а(а) а(6) з— а а(с) (шос1 б). 31.3.2 Перечислите все подгруппы группы е'э и группы е'1з. 31.3.3 Докажите теорему 31.14. 31.3.4 Покажите, что если р — простое число, а е — положительное целое число, то Ф(р ) = р 1(р — 1) .
31.3.5 Покажите, что для любого целого и > 1 и для любого а Е и.„' функция 3о: Щ -+ К„*, определенная как 1" (х) = ах шос( и, представляет собой перестановку Х„'. 990 Часть рП. Избранные ивмы 31.4. Решение модульных линейных уравнений Теперь рассмотрим задачу о решении уравнений вида (31.25) ах = Ь (то<1 п), где а > 0 и и > О. Эта задача имеет несколько приложений. Например, она используется как часть процедуры, предназначенной для поиска ключей для криптографической схемы ВЯА с открытым ключом, описанной в разделе 31.7. Предположим, что для заданных чисел а, 6 и и нужно найти все значения переменной х, которые удовлетворяют уравнению (31.25).
Количество решений может быть равным нулю, единице, или быть больше единицы. Обозначим через (а) подгруппу группы Х„, сгенерированную элементом а. Поскольку (а) = (а<*1: х > 0) = (ах шоб п: х > 0), уравнение (31.25) имеет решение тогда и только тогда, когда [Ь] е (а). Теорема Лагранжа (теорема 31.15) говорит о том, что значение /(а)/ должно быть делителем п. Сформулированная ниже теорема дает точную характеристику подгруппы (а). Теорема 31.2о Для всех положительных целых чисел а и и из 4 = ксб(а, и) следует, что (а) = (4) = (О, с~, 2с(,..., ((п/(М) — 1)И) (31.2б) в Х„, так что )(а)) = и/а. Доиозошельсгиво. Начнем с того, что покажем, что Ы е (а). Вспомним, что ЕХТЕХРЕП-ЕОСЫН(а, и) дает целые числа х' и у', такие, что ах'+ п1/ = 4.
Таким образом, ах' = 4 (шоб и), так что 4 е (а). Другими словами, 4 кратно а из Е„. Поскольку 4 е (а), отсюда следует, что каждое кратное 4 принадлежит (а), так как любое кратное кратного а является кратным а. Таким образом, (а) содержит все элементы множества (О, 4, 24,..., ((и/4) — 1)4), те. (И) С (а). Теперь покажем, что (а) С (4).
Если т е (а), то т = ах шоб и для некоторого целого х, так что т = ах + иу для некоторого целого у. Однако 4 ~ а и 4 ~ и, так что 4 ~ т согласно уравнению (31.4). Следовательно, т Е (4). Объединив полученные результаты, получаем, что (а) = (И). Чтобы увидеть, что ~(а) ~ = п/4, заметим, что между 0 и и — 1 включительно имеется ровно и/И кратных И.
Следствие 31.21 Уравнение ах ь— ч 6 (шоб и) разрешимо относительно неизвестного х тогда и только тогда, когда И ~ Ь, где а = йсй(а, а). 99г Глоеа ЗЬ Георегиико-числовые аегоршиллы Доказательство. Уравнение ах г— в Ь (пюс1 и) разрешимо тогда и только тогда, когда [6] е (а), что то же самое, что (6 пюс) п) Е (О, с(,2с(,..., ((и/Ы) — 1)Ы) согласно теореме 31.20. Если 0 < 6 < и, то Ь е (а) тогда и только тогда, когда с( ] 6, поскольку эти члены (а) являются точными кратными с(.
Если 6 < 0 или 6 ) и, следствие вытекает из наблюдения, что 4 ] Ь тогда и только тогда, когда с1 ] (6 шос( и), поскольку 6 и 6 шос( п отличаются на кратное и, которое само является кратным с(. Следствие 31. 22 Уравнение ах = 6 (шос( и) либо имеет д различных по модулю и решений, где д = 8сс((а, и), либо не имеет решений вовсе. Доказательство. Если ах = Ь (шос( и) имеет решение, то Ь Е (а). Согласио теореме 31.17 огс((а) = ](а)], так что из следствия 31.18 и теоремы 31.20 вытекает, что последовательность а1 шос( п, л' = 0,1,..., периодична с периодом ](а)] = п/с(. Если 6 е (а), то Ь появляется в последовательности а1 шос1 п, 1 = О, 1,..., и — 1, ровно с( раз, поскольку блок значений (а) длиной (и/Н) повторяется ровно с1 раз при увеличении 1 от нуля до п — 1.
Индексы х тех Ы позиций, для югорых ах шос( и = Ь, и являются решениями уравнения ах ив я Ь (шос( и). ° Теорема 31. 23 Пусть с( = ясс((а,п), и предположим, что с1 = ах'+ пу' для некоторых целых чисел х' и у' (например, вычисленных процедурой Ехткипеп-ЕОсс.сц). Если с( ] 6, то уравнение ах = Ь (гпос1 п) имеет в качестве одного из решений значение хо, где хо = х'(6/с() шос( и .
Доказательсюво. Мы имеем ахо = ах'(6/с1) (пюс1 и) = а(6/сл) (пюс( и) (поскольку ах' = д (шос( и)) = Ь (шос1 п), и, таким образом, хо является решением ах =— Ь (гпос1 и). Теорема 31.24 Предположим, что уравнеиие ах = Ь (пюс1 и) разрешимо (т.е. с( ] Ь, где с( = 8сс1(а,п)), и что хо является некоторым решением этого уравнения. Тогда зто уравнение имеет ровно сс различных по модулю п решений, задаваемых соотношением х, = хо+1(п/д) при 1= 0,1,..., с( — 1.
Доказательство. Поскольку и/с( ) 0 и 0 < 1(п/с() < и для 1 = О, 1,..., с1 — 1„ все значения хо, хы..., хе с различны по модулю п. Поскольку хс является ре- 992 Часть Ь76 Избранные темы шепнем ах = — 6 (пюс1 и), мы имеем ахо пюс1 и ь— а 6 (пюс1 п). Таким образом, для з = О, 1,..., с( — 1 имеем ах, пюс1 и = а(хо+ зп/с() шод п = (ахо+ азп/с() шоб и = ахс шос) и (так как из с( ( а следует, что азп/Й кратно п) = Ь (пюй п), а следовательно, ах; = 6 (шос( и), что делает решением также и х,. Согласно следствию 31.22 уравнение ах = 6 (гпос1 и) имеет ровно с( решений, так что все хо,хы...,хб 1 должны быть таковыми.
Теперь у нас имеется математический аппарат, необходимый для решения уравнения вида ах =- Ь (пюз1 и), а ниже приведен алгоритм, который выводит все его решения. На вход алгоритма подаются произвольные положительные целые числа а и и и произвольное целое число 6. М01пл.Ак-1ечеАк-ЕООАт!ОМ-БОечек(а, Ь, и) 1 (з(, х, у ) = ЕхтехпеР-ЕБсшР(а, п) 2 Ыз1)Ь 3 хо = х'(Ь/с() пюд и 4 1ог з = 0 го с( — 1 5 рпп1 (хр + з(п/з()) пюд и б е1ае ргшг "решений нет*' В качестве примера работы этой процедуры рассмотрим уравнение 14х ьа 30 (пюд 100) (здесь а = 14, Ь = 30 и п = 100). Вызвав в строке 1 процедуру Ехтемпеп-Еисшп, получаем (з(, х', р') = (2, — 7,1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
