Рис. 33.2 33.2 (а) Группа вычетов по модулю 6 по сложению (Ж,в, +б). (Ь) Группа обратимых вычетов по модулю 15 по умножению (Ze, -is).

Теорема 33.12

Система (Zra, является конечной абелевой группой. Доказательство.

Ассоциативность и коммутативность операции +га следуют из аналогичных свойств сложения целых чисел. Нейтральным элементом является 0 (точнее говоря, [0]„). Обратным (относительно групповой операции) элементом к а (точнее, [а]п) служит ( - а) (то есть, [-а]п или [га - а]п).

Несколько сложнее определяется мультипликативная группа вычетов по модулю га (mutiplicative group modulo п). Элементы этой группы образуют множество Z*, состоящее из элементов Zra, взаимно простых с га. Понятие взаимной простоты имеет смысл (не зависит от выбора представителя в классе эквивалентности): если к - целое число, то НОД(а, га) = 1 равносильно НОД(а-\-кп, га) = 1 (упр. 33.2-3).

В качестве примера рассмотрим случай га = 15 (рис. 33.2 (Ь), где перечислены элементы соответствующей группы и показана таблица умножения).

Теорема 33.13

Система (Z*, -п) является конечной абелевой группой. Доказательство.

Проверим, что любой элемент имеет обратный в смысле групповой операции. (Нейтральным элементом является класс [1].) Чтобы найти обратный к элементу а, рассмотрим тройку (d, х,у), выдаваемую процедурой Extended-Euclid (а, га). Поскольку а £ Z* , числа а и га взаимно просты и d = НОД(а, Ъ) = 1, поэтому ах + пу = 1 и ах = 1 (mod га). Таким образом, элемент [х]п является обратным к [а]п в группе (Z*, •„). Единственность обратного можно доказать (как и для любой группы) следующим образом: если жиж обратны к а, то (ж © а) ф ж = е © ж = ж, а переставив скобки по ассоциативности, получим ж ф (а ф ж) = ж ф е = ж,

В дальнейшем мы для простоты будем обозначать сложение и умножение по модулю обычными знаками + и • (иногда опуская знак умножения), а аддитивную и мультипликативную группы вычетов по модулю га будем обозначать Ъп и Z* (не упоминая групповую операцию). Элемент, обратный (относительно операции умножения) к а, мы будем обозначать a~l mod га. Как обычно, частное а/Ъ в Z* определяется как ab~l (mod га). Например, в Ъ\ъ имеем 7-1 = 13 (mod 15), поскольку 7 • 13 = 91 = 1 (mod 15), откуда 4/7 = 4 • 13 = 7 (mod 15).

Число элементов в Z* обозначается <~р(п). Функция (р называется ip-функцией Эйлера (Eulers phi function). Можно доказать такую

формулу для функции Эйлера:

v(») = »(i-l).....(i-l)

(33.20)

где pi,... ,ps - список всех простых делителей числа га. Можно пояснить эту формулу так: случайное число t взаимно просто с га, если оно не делится на р\ (вероятность чего есть (1 - 1/pi), не делится на р2 (вероятность (1 - 1/р2) и т.д., а события эти независимы.

Например, у (45) = 45(1 - 1/3) (1 - 1/5) = 24, поскольку простыми делителями числа 45 являются числа 3 и 5. Для простого числа р имеем

так как все числа 1, 2,... ,р - 1 взаимно просты с р. Если число га составное, то <~р(п) < га - 1. Подгруппы.

Пусть (S, ф) является группой, a S С S. Если (S, ф) тоже является группой, то (S1, ф) называют подгруппой (subgroup) группы (S, ф). Например, чётные числа образуют подгруппу группы целых чисел (с операцией сложения).

Теорема 33.14

Замкнутое подмножество конечной группы является подгруппой: если (S, ф) - конечная группой, S С S и а ф Ь £ S для любых а, Ь £ S, то (S1, ф) является подгруппой группы (S, ф).

Доказательство

оставляется читателю (упр. 33.3-2).

Пример: множество {0,2,4,6} С Zs замкнуто относительно сложения и образует подгруппу группы Ъ%.

Следующая теорема накладывает на размер подгрупп важные ограничения.

Теорема 33.15 (Теорема Лагранжа)

Если (S1, ф) является подгруппой конечной группы (S, ф), то \S\ делит \S\.

Доказательство

можно найти в учебниках алгебры (группа S разбивается на непересекающиеся классы вида жфб", каждый из которых содержит ll элементов).

Подгруппа S группы S, не совпадающая со всей группой, называется собственной (proper) подгруппой. Следствие 33.16

Если S является собственной подгруппой конечной группы S,

Это (очевидное) следствие теоремы Лагранжа будет использовано при анализе вероятностного алгоритма Миллера - Рабина (проверка простоты).

то < \S\ 2.

Подгруппа, порождённая элементом группы.

Пусть а - некоторый элемент конечной группы S. Рассмотрим последовательность элементов

е,а,афа,афафа,...

По аналогии со степенями (групповая операция соответствует умножению) будем писать а(°) = е, aW = a, a(2) = а © a, a(3) = a © a © a и т.д. Легко видеть, что ф = а1+3\ в частности, aW ©a = a(8+1). Аналогичное утверждение можно сформулировать и для «отрицательных степеней», в частности, aW • a-1 = a(8 1). Если группа S конечна, то последовательность

е,а,афа,афафа,...

будет периодична (следующий элемент определяется предыдущим, поэтому раз повторившись, элементы будут повторяться по циклу). Предпериода при этом не будет, так как каждый элемент может быть получен из следующего (применением групповой операции к нему и к а-1) и потому перед равными элементами идут равные. Таким образом, последовательность имеет вид

e = a(°),aW,a(2),...aW = e,...

(дальше всё повторяется) и содержит t различных элементов, где t - наименьшее положительное число, для которого = е. Это число называется порядком (order) элемента а и обозначается ord(a).

Указанные п элементов образуют подгруппу. Это следует из теоремы 33.14, кроме того, это можно проверить непосредственно, так как групповая операция соответствует сложению «степеней». Эта подгруппа называется порождённой элементом a (subgroup generated by а) и обозначается (а) или, если мы хоти явно указать групповую операцию, ((a),©). Элемент а называют образующей (generator) подгруппы (а); говорят, что он порождает (generates) эту подгруппу. Например, элемент а = 2 группы Ziq порождает подгруппу, состоящая из элементов 0,2,4.

Вот несколько подгрупп группы Iiq, порождённых различными элементами: (0) = {0}, (1) = {0,1,2,3,4,5}, (2) = {0, 2, 4}. Аналогичный пример для мультипликативной группы Z7: здесь (1) = {1}, (2) = {1, 2, 4}, (3) = {1,2, 3,4, 5, 6}.

Из сказанного нами вытекает

Теорема 33.17

Пусть (S, ф) - конечная группа. Если а £ S, то размер подгруппы, порождаемой а, совпадает с порядком а (то есть, \{а)\ = ord(a)).

Следствие 33.18

Последовательность aW, а2\ ... периодична с периодом t = ord(a); иначе говоря, = а тогда и только тогда, когда г = j (mod t).