Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 198
Текст из файла (страница 198)
Конечные группы Грунин (8топр) (Я, 9) — это множество Я, для элементов которого определена бинарная операция 9, обладающая перечисленными ниже свойствами. 1. Замкнутость: для всех элементов а, Ь Е Я имеем а 9 Ь Е 5. 2. Существование единицьп существует элемент е е Я, который называется единичным (Ыеппйу) элементом группы; для этого элемента и любого элемента а Е Я выполняется соотношение е 9 а = а 9 е = а.
3. Ассоциативность: для всех а, Ь, с е Я выполняется соотношение (а 9 Ь) 9 9 с = а 9 (Ь 9 с). 4. Существование обратного элемента: для каждого элемента а е Я существует единственный элемент ЬЕ Я (он называется обратным (шчегзе) к элементу а), такой что а 9 Ь = Ь 9 а = е. В качестве примера рассмотрим уже знакомую нам группу (2, +) целых чисел с операцией сложения: в ней единичный элемент — О, а обратный элемент к любому числу а — число — а.
Если группа (Я, 9) обладает свойсн4ваи каимун4ативности (сопшш1айче 1ав) а 9 Ь = Ь 9 а для всех а, Ь Е Я, то это абелевн груннв (аЪе11ап 8гопр). Если группа (Я, 9) удовлетворяет условию ~Я! < оо, т.е. количество ее элементов конечно, то она называется конечной (Йпйе 8гопр). Глава 31.
Теоретико-числовые алгоритмы 969 Группы, образованные сложением и умножением по модулю С помощью операций сложения и умножения по модулю и, где и — положительное целое число, можно образовать две конечные абелевы группы. Эти группы основаны на классах эквивалентности целых чисел по модулю и, определенных в разделе 31.!. Чтобы определить группу над множеством классов Е„, нужно задать подходящие бинарные операции, полученные путем переопределения обычных операций сложения и умножения.
Операции сложения и умножения над Е„определить легко, поскольку классы эквивалентности двух целых чисел однозначно определяют класс эквивалентности их суммы или произведения. Другими словами, если авва'(шос)и) и 6= 6'(тос1и), то а + Ь = а' + Ь'(пюс)и), ссЬ = а'Ь'(пюс(и) . Таким образом, операций сложения и умножения по модулю и, которые мы обозначим как +„и „, определяются следующим образом: [а]„+„[6]и = [а+ 6]„, [а]„„[Ь]„= [аЬ]„. (31.18) (Вычитание в Е„можно легко определить как [а]„— „[Ь]„= [а — Ь]„, однако с делением, как мы сможем вскоре убедиться, дело обстоит сложнее.) Эти факты подтверждают удобную общепринятую практику использования наименьшего неотрицательного элемента каждого класса эквивалентности как представительного при вычислениях в Е„.
Сложение, вычитание и умножение над представителями классов выполняется как обычно, но затем каждый результат х заменяется соответствующим представителем класса эквивалентности (т.е. величиной х пюс1 и). На основе определения операции сложения по модулю и определяется аддипсиепап гРУппа по модУлю и (асЫ111че 8гоиР шос1и1о и) (Есо +„). РазмеР аддитивной группы по модулю и равен ]Е„[ = и.
В табл. 31.2 представлены результаты выполнения операций в группе (Еа, +а). Теорема 31.12. Система (Е„, +„) образует конечную абелеву группу. Дсоказапсгльспсво. Из уравнения (31.18) следует замкнутость группы (Е„, +„). Ассоциативность и коммутативность операции +„следует из ассоциативности Часть Ч!!. Избранные темы 970 и коммутативности операции +: ([а]„+„[Ь]„) +„[с)„= [а+ Ь]„+„[с]„= = [(а + 6) + с]„= = [а+ (Ь+ с))„= = [а]„+„[Ь+ с]„= = [а]„+„([6]„+„[с]„), [а)„+„[Ь]„= [а+ Ь]„= = [Ь+ а]„= = [6]„+„[а)„.
В роли единичного элемента (Е„, +„) выступает 0 (т.е. класс [0]„). Элемент, аддитивно обратный элементу а (т.е. классу [а) „), представляет собой элемент — а (те. класс [-а)„или [и — а]„), поскольку [а)„+„[ — а)„= [а — а]„= [0]„. ° На основе операции умножения по модулю и определяется мульюиплпквтивпап группа по модулю и (шп!!!р!!санте йгоир шест!о и) (Е„*,.„). Элементы этой группы образуют множество Е„', образованное из элементов множества Е„, взаимно простых с и: Е„' = ([а]„Е Е„: йсй (а, и) = Ц. Чтобы убедиться, что группа Е„' вполне определена, заметим, что для 0 < а < и при всех целых !с выполняется соотношение а = (а+ !си) (шайи). Поэтому из йод(а, и) = 1, согласно результатам упражнения 3 1.2-3, для всех целых /с следует, что бей (а + ик, и) = 1. Поскольку [а]„= (а + )си: к Е Е), множество Е„' вполне определено. Примером такой группы является множество Е1ь — — (1, 2, 4, 7, 8, 11, 13, 14), в качестве групповой операции в которой выступает операция умножения по модулю 15.
(Здесь элемент [а]„ь обозначается как а; например, элемент [7], обозначается как 7.) В табл. 31.3 показаны результаты выполнения операции для данной группы. Например, 8 . 11 аа 13 (шой15). Единичным элементом в этой группе является 1. Теорема 31.13. Система (Е,"„„) образует конечную абелеву группу. Доказаюельсиюво. Замкнутость (Е„',;,) следует из теоремы 3!.б.
Ассоциативность и коммутативность для операции;, можно доказать аналогично доказательству этих свойств для операции +„в теореме 3 !.12. В роли единичного здесь Глава 31. Теоретико-числовые алгоритмы 971 Таблица 31.2. Группа (Еа, +а) Таблица 31.3. Группа (Я~м и) выступает элемент [1]„. Чтобы показать наличие обратных элементов, предположим, что а — элемент множества Е„*, а набор чисел (Н, х, у) — выходные данные процедуры Ехтечпнп Еос~.лэ(а, и).
Тогда д = 1, поскольку а Е Е„" и справедливо равенство ах+ пу = 1, или, что то же самое, ах = 1 (щооп) . Таким образом, класс [х]„— обратный классу [а]„относительно операции умножения по модулю и. Доказательство того, что обратные элементы определяются однозначно, отложим до рассмотрения следствия 31.26. И В качестве примера вычисления мультипликативных обратных элементов рассмотрим случай а = 5 и п = 11, Процедура Ехтньлзнэ Епс1Лэ(а, п) возвращает тройку чисел (с1,х,у) = (1, — 2,1), так что 1 = 5 (-2) + 11 1. Таким образом, число -2 (т.е.
9 пюг1 11) — мультипликативное обратное по модулю 11 к числу 5. Часть Ч11. Избранные темы 972 Далее в оставшейся части этой главы, когда речь будет идти о группах (Е„, +„) и (Е'„, „), мы будем обозначать классы эквивалентности представляющими их элементами, а операции +„и „вЂ” знаками обычных арифметических операций + и (последний знак может опускаться) соответственно. Кроме того, эквивалентность по модулю и можно интерпретировать как равенство в г.„.
Например, оба выражения, приведенные ниже, обозначают одно и то же: ах = 5(тайп), [а]„ „ [х]„ = [Ь]„ . Для дальнейшего удобства иногда группа (Я, ш) будет обозначаться просто как Я, а из контекста будет понятно, какая именно операция подразумевается. Таким образом, группы (2„, +„) и (Е;„.„) будут обозначаться как 2„и Е„' соответственно. Элемент, обратный (относительно умножения) к элементу а, будет обозначаться как (а 1 тос1 и). Операция деления в множестве Е„' определяется уравнением а/5— : аб 1(тог1п). Например, в множестве Еш 7 ~ = 13 (тос(15), поскольку 7 13 ив э 91 = 1(п1ос115), поэтому 4/7 е— э 4 13 = 7(п1од15).
Обозначим размер множества г;, как ф(п). Эта функция, известная под названием ф-функции Эйлера (Еи!ег'з рЫ йшсг1оп), удовлетворяет уравнению (31.19) где индекс р пробегает значения всех простых делителей числа и (включая само и„ если оно простое). Здесь мы не станем доказывать эту формулу, а попробуем дать для нее интуитивное пояснение. Выпишем все возможные остатки от деления на п — (О, 1,..., п — Ц, а затем для каждого простого делителя р числа п вычеркнем из этого списка все элементы, кратные р.
Например, простые делители числа 45— числа 3 н 5, поэтому ф (45) = 45 1 — — 1 — — = 45 — — = 24. Если р — простое число, то Е„" = (1,2,...,р — Ц и ф(р) = р — 1. (31.20) Если же п — составное, то ф (и) ( п — 1. Подгруппы Если (Я, ®) — группа, У С Я и (У, Ю) — тоже группа, то (У, 03) называется подгруппой (зцЬягоир) группы (Я,(9). Например, четные числа образуют подгруппу группы целых чисел с операцией сложения. Полезным инструментом для распознавания подгрупп является сформулированная ниже теорема. Глава 31. Теоретико-числовые алгоритмы 973 Теорема 31.14.
(Непустое замкнутое подмножество конечной группы является подгруппой). Если (Я, Ю) — конечная группа, а У вЂ” любое непустое подмножество множества Я, такое что а Ю Ь б У для всех а, 6 Е У, то (У, Ю) — подгруппа группы (Я, ®). Доказапсельспсво. Доказать эту теорему читателю предлагается самостоятельно в упражнении 31.3-2. И Например, множество (0,2,4,6) образует подгруппу группы Еа, поскольку оно непустое и замкнутое относительно операции + (т.е. оно замкнуто относительно операции +в).
Сформулированная ниже теорема крайне полезна для оценки размера подгруппы; доказательство этой теоремы опущено. Теорема 31.15 (Теорема Лагранжа). Если (Я, 9) — конечная группа, и (У, Ю)— ее подгруппа, то (У) — делитель числа !Я!. И Подгруппу У группы Я называю~ истинной (ргорег) подгруппой, если У ф Я. Приведенное ниже следствие из этой теоремы окажется полезным при анализе теста простых чисел Миллера-Рабина (Мй!ег-йаЬ1п), описанного в разделе 31дй Следствие 31.16. Если У вЂ” истинная подгруппа конечной группы Я, то ~У~ < < ф)/2. И Подгруппы, сгенерированные элементом группы Теорема 3! .14 обеспечивает интересный способ, позволяющий сформировать подгруппу конечной группы (Я, 9).
Для этого следует выбрать какой-нибудь элемент группы а и выделить все элементы, которые можно сгенерировать с помощью элемента а и групповой операции. Точнее говоря, определим элемент а1Я1 дляк) 1как Например, если в группе Еа задать элемент а = 2, то последовательность а01, а!~1,...
имеет вид 2,4,0,2,4,0,2,4,0,.... В группе Е„справедливо соотношение а!"1 = ка шос! и, а в группе Е,*, — соотношение а!"1 = аь шос! п. Подгруппа, сгенерированная элементом а (зцЬйгоир йепегагеб Ьу а) обозначается как (а) или ((а), Ю) и определяется следующим образом: (а) = (а! 1:/с>1).
974 Часть Ч11. Избранные темы Говорят, что элемент а генерируем (8епега1ез) подгруппу (а) или что а — генератор (8епегагог) подгруппы (а). Поскольку множество Я конечное, то (а)— конечное подмножество множества Я, которое может содержать все элементы множества Я. Поскольку из ассоциативности операции Ю следует соотношение ас') Е ао) Ои-У) то подмножество (а) — замкнутое и, согласно теореме 31.14, (а) — подгруппа группы Я. Например, в группе Еа справедливы соотношения (0) = (О), (1) = (0,1,2,3,4,5), (2) = (0,2,4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
