Циклическая группа
Например, если G = <e, g 1 , g 2 , g 3 , g 4 , g 5 >, то G циклическая. В этом случае можно заметить, что G устроена также, как и группа <0, 1, 2, 3, 4, 5>с операцией сложения по модулю 6 (говоря формально, G изоморфна ей). Изоморфизм строится, если в соответствие g поставить 1 из второй группы.
Содержание
Свойства [ ]
- G абелева; то есть групповая операция коммутативна: ab = ba. Это верно, поскольку (a + b) mod n = (b + a) mod n.
- Если n < ∞ <\displaystyle \infty >, то g n = e <\displaystyle g^
=e> , поскольку n mod n = 0. - Если же n = ∞ <\displaystyle \infty >, то существуют только два порождающих элемента: 1 и -1 (в обозначениях ( Z , + ) <\displaystyle (\mathbb
,+)> ). - Каждая подгруппа G циклична.
- Gn изоморфна Z / n Z <\displaystyle \mathbb
/n\mathbb > (факторгруппа Z <\displaystyle \mathbb > по n Z <\displaystyle n\mathbb > ), поскольку Z / n Z <\displaystyle \mathbb /n\mathbb > = <0 + n Z <\displaystyle n\mathbb > , 1 + n Z <\displaystyle n\mathbb > , 2 + n Z <\displaystyle n\mathbb > , …, n — 1 + n Z <\displaystyle n\mathbb > > ≅ <\displaystyle \cong ><0, 1, 2, 3, 4, … n - 1>с сложением по модулю n.
Если p — простое число, то группа порядка p циклическая и единственна с точностью до изоморфизма (это следует из теоремы Лагранжа).
Основная теорема о конечнопорождённых абелевых группах утверждает, что любая конечнопорождённая абелева группа единственным образом разлагается в прямое произведение примарных циклических групп. Примарной группой может быть циклическая группа Z p n <\displaystyle \mathbb
Z n <\displaystyle \mathbb
> — конечное поле, также обозначаемое Fp или GF(p). Каждое конечное поле с p элементами изоморфно Fp.
Мультипликативная группа любого конечного поля является циклической (она порождается элементом поля наибольшего порядка).
Примеры [ ]
нейтральный элемент группы, а остальные элементы располагаются по кругу в порядке возрастания степени образующего элемента.
2.2. Подгруппы
Определение 2.7. Подгруппой в группе ( G , ) называется всякое непустое подмножество H элементов множества G, которое в свою очередь является группой относительно той же операции.
Тот факт, что H есть подгруппа группы G отмечают так: H ≤ G или H < G , есть включение H G – строгое.
Пример 2.7. Аддитивные группы целых, рациональных, вещественных и комплексных чисел образуют систему подгрупп: ( Z , +)<( Q , +)<( R , +)<( C , +).
Подмножество всех целых чисел, делящихся на натуральное число n > 1, образует подгруппу в группе целых чисел с операцией сложения. Эту подгруппу обозначают через ( nZ , +). Следовательно, имеют место бесконечные цепочки аддитивных подгрупп типа ( Z , +)>(2 Z , +)>(4 Z , +)> … .
Теорема 2.1 (критерий подгруппы). Непустое подмножество H группы ( G , ) является подгруппой тогда и только тогда, когда для произвольных эле-
ментов a , b H имеет место включение a b − 1 H .
Пример 2.8. В силу критерия в любой группе G подмножество < e >из одного нейтрального элемента e этой группы является подгруппой.
Определение 2.8. Подгруппа H группы G называется собственной, если
Пример 2.9. С помощью критерия легко убедиться, что SL n ( R ) – под-
множество квадратных матриц порядка n с определителем, равным 1, образуют подгруппу в GL n ( R ) . Действительно, для произвольных матриц A , B SL n ( R )
по свойствам определителей det ( B − 1 ) = 1 и det ( AB − 1 ) = det A det ( B − 1 ) = 1. Следовательно, A , B − 1 SL n ( R ) и согласно критерию 2.3.1 SL n ( R ) является подгруппой в группе GL n ( R ) .
2.3. Циклические группы и подгруппы
Теорема 2.2. Пусть a – фиксированный элемент произвольной группы G. Пусть 
a 
= < a 0 = e , a , a 2 , K , a − 1 , a − 2 , K >– множество всевозможных степеней элемента a. Тогда 
a 
– подгруппа группы G, причем абелева.
Доказательство следует из критерия подгруппы: для произвольных a k , a − e 
a 
произведение a k a − e = a k − e принадлежит, очевидно, множеству
a 
.
Определение 2.9. Подгруппа 
a 
из теоремы 2.2 называется циклической
подгруппой группы G, порожденной элементом a. Если в группе G найдется такой элемент b, что G = b , то такую группу называют циклической.
Пример 2.10. Следующие группы являются циклическими: ( Z , + ) = 
1 
;
( Z / nZ , + ) = 
1 
.
Теорема 2.3. Пусть элемент a G обладает свойством: a n = e для некоторого целого n и a k ≠ e для всех целых k , 1 ≤ k < n . Тогда циклическая подгруппа 
a 
имеет порядок n и 
a 
= < a , a 2 , K , a n = e >.
Доказательство. Для целых k , 1 ≤ k < n , ( a k ) − 1 = a n − k .
Определение 2.10. Величина n из теоремы 2.3 называется порядком элемента a G . Если же для элемента a G такого n не существует, то говорят, что элемент имеет бесконечный порядок.
Пример 2.11. Любое ненулевое целое число имеет бесконечный порядок в аддитивной группе целых чисел.
Пример 2.12. Возьмем матрицу
GL ( R ) . Здесь A 2 =
… . Степени матрицы A попарно различны и образуют бесконеч-
ную последовательность. Определитель матрицы A равен 1
, … . Таким образом, циклическая подгруппа, порожденная мат-
( R ) , является бесконечной.
рицей A в группе GL 2
Пример 2.13. Матрица
– единичная матрица. Соглас-
но теореме 2.3 подгруппа 
H 
есть конечная подгруппа порядка четыре.
Теорема 2.4. Всякая циклическая группа – абелева.
Теорема 2.5. Всякая подгруппа циклической группы является цикличе-
Итак, в любой группе много циклических подгрупп: каждый элемент порождает свою циклическую подгруппу. Тем не менее, следует заметить, что чаще группы циклическими не являются. Например, все некоммутативные
группы не могут быть циклическими. Циклическими не являются аддитивные и мультипликативные группы вещественных и комплексных чисел в силу их несчетности. Множество рациональных чисел счетно, то есть равномощно множеству целых чисел. Однако абелева группа ( Q , +) в отличие от группы ( Z , +) из примера 2.10 также не циклична, т.к. для каждого рационального числа
не содержит рациональных
несократимых дробей r s , r Z , s N , у которых знаменатель s > m , следова-
тельно, 
q 
≠ ( Q , + ) .
Теорема 2.6. Для каждого простого числа p мультипликативная группа Z / pZ * содержит p – 1 элементов и является циклической.
Проблема нерешенная [16]: конечно или бесконечно множество простых чисел p , для которых Z / pZ * = 
2 
, т.е. мультипликативная группа Z / pZ * совпадает с циклической подгруппой, порожденной классом вычетов
2.4. Смежные классы по подгруппе
Определение 2.11. Пусть H – собственная подгруппа группы ( G , ) . Пусть a G . Через aH обозначим множество элементов < ah | h H >и назо-
вем его левым смежным классом группы G по подгруппе H.
Если существует b G , b H aH , можно построить новый левый
смежный класс bH и так далее. Аналогично строят правые смежные классы. Если каждый левый смежный класс совпадает с правым: aH = Ha , то тогда смежные классы называют двусторонними. Такими являются смежные классы в любой абелевой группе G . Смежные классы обладают рядом важных свойств, которые отражает
Теорема 2.7. Пусть H – собственная подгруппа группы G. Тогда:
1) каждый элемент g G принадлежит какому-нибудь левому смежно-
му классу по подгруппе H;
2) два элемента a , b G принадлежат одному левому смежному классу
тогда и только тогда, когда a − 1 b H ;
3) любые два левых смежных класса либо не пересекаются, либо совпадают;
4) для всякого a G мощности множеств aH и H совпадают;
5) G есть объединение попарно непересекающихся левых (правых) смежных классов по подгруппе H.
Пример 2.14. Пусть G = M 1 × 4 ( Z / 2 Z ) – множество всевозможных строк-
матриц с четырьмя координатами из Z / 2 Z . Это группа по сложению. Обычно ее обозначают через V 4 . Легко проверить, что множество
0 0 )( , 1 0 1 1 ) , ( 0
образует подгруппу в
14 2 43 14243 1 4 243 14243
группе V 4 . Очевидно, G = 24 = 16, H = 4 . Согласно теореме 2.7 группа G пред-
ставляет собой объединение четырех смежных классов по подгруппе H . Эти классы представлены в таблице.
Смежные классы группы G по подгруппе H
Лемма 2.3. Пусть H – собственная подгруппа группы G. Мощности множеств всех левых и соответственно правых смежных классов группы G по подгруппе H равны.
Доказательство. Построим соответствие между названными множествами по правилу gH ↔ Hg . Очевидно, такое соответствие является взаимно одно-
значным, что и доказывает лемму.
Доказанное утверждение позволяет ввести следующее
Определение 2.12. Индексом подгруппы H в группе G называется мощность множества всех смежных классов группы G по данной подгруппе и обозначается через G : H .
Пример 2.15. Индекс подгруппы ( nZ , +) в группе ( Z , +) равен n . Действительно, в данном случае множество всех смежных классов есть множество
Замечание. Таблицы смежных классов играют важную роль в теории и практике помехоустойчивого кодирования. Простейший метод коррекции ошибок базируется на основе таблиц смежных классов, аналогичных приведенной выше. В современных цифровых каналах связи принято информацию передавать в виде двоичных блоков с определенной фиксированной длиной n , то есть n -мерных векторов с координатами из Z / 2 Z . Они получаются разбиением исходной информации, уже преобразованной в двоичный текст, на блоки по k двоичных символов, k < n . К каждому k -мерному блоку присоединяется специальным образом n − k проверочных разрядов. В результате предназначенные для передачи слова принадлежат некоторому k -мерному подпространству H пространства V n всех n -мерных векторов. С точки зрения теории групп H –
подгруппа аддитивной группы V n . Ее называют группой кодовых слов. В про-
цессе передачи по каналу связи конкретного кодового слова h может наложиться «шум» – некоторый n -мерный двоичный вектор e V n . Тогда принятое
по каналу связи слово-сообщение x = h + l является одним из элементов таблицы смежных классов группы V n , образующая смежного класса и есть наложив-
Циклическая группа
Любая циклическая группа абелева, т.к. степени одного и того же элемента коммутируют между собой.
Примерами циклических групп являются группы [math]\mathbb
Классификации циклических групп
Доказательство разбивается на два случая: порядок [math]a[/math] конечен или бесконечен.
Пусть порядок [math]a[/math] бесконечен. Тогда рассмотрим отображение [math]\phi:\mathbb
Пусть теперь порядок [math]a[/math] конечен и равен [math]r[/math] . Рассмотрим отображение [math]\phi:\mathbb
[math]\phi(c) = \phi(n+m-k\cdot r)=a^
[math]\phi[/math] сюръективно по определению циклической группы. Докажем инъективность. Пусть [math]a^n=a^m,\, n\lt m\lt r[/math] , тогда
Подгруппы
Определение. Дискретным логарифмом l числа b при основании a по модулю p называется степень, в которую нужно возвести число a, чтобы получить число b:
b = a l mod p.
Другое название дискретного логарифма l – индекс числа b при основании a по модулю p.
Принятые обозначения: log a b и ind a b.
Определение. Наименьшая степень, в которую нужно возвести число a по модулю p, чтобы получить 1, называется порядком числа a. Обозначение — ord a.
Утверждение. Пусть p – простое число. Максимальный порядок числа по модулю p равен p – 1.
Утверждение. Пусть p – простое число, параметры a, b удовлетворяют неравенствам 1< a, b < p. Тогда сравнение b = a x mod p имеет единственное решение относительно x, если порядок числа a равен p – 1.
1. Вычисляем значения a k mod p для k = 1, 2, 3, … до выполнения равенства b = a k mod p.
2. Значение k, при котором выполняется сравнение b = a k mod p, является дискретным логарифмом.
3. x:= k.
Алгоритм больших — малых шагов (Шенкса)
Пусть n — порядок числа a.
1. Вычисляем m:= é n ù, где é n ù — округление с избытком.
2. Строим таблицу пар (j, a j ) для j = 0, 1, 2, m -1.
3. Вычисляем t:= a – m , решая сравнение a m × t = 1 mod p.
5. Цикл по i от 0 до m – 1
проверяем, является ли g второй компонентой в таблице п.2
если g = a j , то полагаем x = m × i + j
Пусть n — порядок числа a.
1. Число n представляем в виде n = q × r, q – простое число.
2. Вычисляем значения a 1:= a r mod p, b 1:= b r mod p.
3. С помощью алгоритма больших — малых шагов находим y, решая сравнение
b 1:= a 1 y mod p, ord a 1 = q.
4. Вычисляем t:= a – y , решая сравнение a y × t = 1 mod p.
5. Вычисляем значения a 2:= a q mod p, b 2:= b × t mod p.
6. С помощью алгоритма больших — малых шагов находим z, решая сравнение
b 2:= a 2 z mod p, ord a 2 = r.
7. x = z × q + y
1. Дайте определение дискретного логарифма.
2. Дайте определение порядка числа.
3. Сформулируйте условия существования дискретного логарифма.
4. Опишите переборный алгоритм дискретного логарифмирования.
5. Опишите алгоритм больших — малых шагов.
6. Опишите алгоритм Нечаева – Поллига — Хеллмана.
7. В каких криптографических алгоритмах необходимо решать задачу дискретного логарифмирования?
Определение. Группа (G, *) состоит из множества G, на котором определена бинарная операция *, удовлетворяющая трем аксиомам:
- Операция * в группе ассоциативна: для любых элементов a, b, и c из G выполняется равенство
a *(b * c) = (a * b)* c.
- В множестве G существует такой единичный элемент e, что
e * a = a * e = a.
- Для каждого элемента a Î G существует обратный элемент a –1 Î такой, что
a * a –1 = a –1 * a = e.
Определение. Группа (G, *) называется коммутативной (абелевой), если для любых элементов a, b, и c из G выполняется равенство
a * b = b * a.
Если в качестве бинарной операции определена операция умножения ´, то группа называется мультипликативной, единичный элемент e = 1, обратный элемент обозначается a –1 или 1 / a.
Если в качестве бинарной операции определена операция сложения +, то группа называется аддитивной, единичный элемент e = 0, обратный элемент обозначается – a.
Из аксиом группы можно вывести, что в группе существует только один единичный элемент. Можно доказать также и единственность обратного элемента для всякого элемента группы.
Определение. Группа (G, *) называется конечной, если число элементов множества G конечно. В этом случае число элементов множества G называется порядком группы (G, *).
Взаимно однозначные преобразования любого множества образуют группу относительно операции умножения преобразований.
1. Множество всех ненулевых действительных чисел относительно операции умножения – «мультипликативная группа действительных чисел» R * .
2. Множество всех целых чисел относительно операции сложения – «аддитивная группа целых чисел» Z.
3. Множество всех векторов в пространстве R n относительно операции сложения векторов.
4. Множество всех многочленов с действительными коэффициентами относительно операции сложения многочленов.
Группы в примерах 1-4 имеют бесконечно много элементов.
Множество Z n
Пусть n – натуральное число. Введем на множестве целых чисел Z операцию сравнения по mod n: a mod n, a Î Z. Операция сравнения по mod n разбивает множество Z на классы эквивалентности, соответствующие остаткам от деления целых чисел на n: 0, 1, 2, …, n–1. Множество классов эквивалентности по mod n образует множество Z n. Все арифметические операции < +, –, ´,: >в Z n выполняются по mod n.
Пример. Рассмотрим множество Z 25 = < 0, 1, 2,…, 24 >. Для элементов этого множества имеем 13 + 16 = 4, 13 ´ 4 = 2, 13 – 16 = 22, 15: 2 =?
Определение. Пусть a Î Z n. Мультипликативным обратным элементом элемента a по mod n называется элемент a – 1 , такой что a ´ a – 1 = 1 mod n. Элемент a называется обратимым по mod n, если для него существует обратный.
Деление в Z n определяется как умножение на обратный элемент a: b = a ´ b – 1 , если делитель b обратим.
Пример. В множестве Z 25 2 – 1 = 13, т.к. сравнение 2 x = 1 mod 25 дает решение x = 13. Отсюда 15: 2 = 15 ´ 2 – 1 = 15 ´ 13 = 195 = 20 mod 25.
Утверждение. Элемент a Î Z n обратим в том и только том случае, когда a и n взаимно просты, (a, n) = 1.
Пример. Обратимые элементы в Z 9: 1, 2, 4, 5, 7, 8. Для определения 5 –1 решаем сравнение 5 x = 1 mod 9,которое дает решение x = 2. Отсюда 5 – 1 = 2.
Множество Z n с операцией сложения по mod n образует конечную аддитивную группу порядка n.
Введем множество Z n * , определяемое как подмножество множества Z n, состоящее только из обратимых элементов
Z n * = < a Î Z n | (a, n) = 1 >
Множество Z n * с операцией умножения по mod n образует конечную мультипликатив-ную группу порядка j (n).
Если n – простое число, то j (n) = n – 1 и Z n * = < 1, 2, 3, …, n – 1 >.
Определение. Пусть a Î Z n * . Порядком элемента группы называется наименьшая степень t, в которую нужно возвести элемент, чтобы получить 1:
a t = 1 mod n.
Обозначение t = ord (a).
Утверждение. Если ord (a) = t и a s = 1 mod n, то s делится на t.
Утверждение. Если t – порядок некоторого элемента a Î Z n * , то j (n) делится на t.
Определение. Если ord(a) = j (n) для a Î Z n * , то элемент a называется образующим, или примитивным, элементом группы.
Если в группе есть образующий элемент, то группа называется циклической.
Утверждение. Всякая циклическая группа абелева.
Свойства образующих (примитивных) элементов мультипликативной группы Z n *
1. Группа Z n * имеет образующий элемент в том и только том случае, когда
n = 2, 4, p k , 2 p k , p – простое нечетное число.
2.Если a – образующий элемент Z n * , то
3.Если a – образующий элемент Z n * , то b = a i mod n является образующим элементом в том и только том случае, когда i взаимно просто с j (n), (i, j (n)) = 1.
4.Если Z n * – циклическая группа, то число образующих элементов группы равно j (j (n)).
5.Элемент a Î Z n * является образующим элементом группы в том и только том случае, когда
a j (n)/ p ¹ 1 mod n
для любого простого делителя p числа j (n).
В группе Z 21 * j ( 21 ) = (3 – 1) (7 – 1) = 12 элементов: 1,2,4,5,8,10,11,13,16,17,19,20. Каждый элемент имеет обратный, например, 2 – 1 = 11, 10 – 1 = 19. Группа не является циклической. Ord (1) = 1, ord (8,13,20) = 2, ord (4,16) = 3, ord (2,5,10,11,17,19) = 6.
В группе Z 25 * j ( 25 ) = 5 (5 – 1) = 20 элементов. Группа циклическая, содержит j (j ( 25 )) = j ( 20 ) = 2 (2 – 1) (5 – 1) = 8 образующих.
В группе Z 13 * j ( 13 ) = 13 – 1 = 12 элементов. Группа циклическая, содержит j (j ( 13 )) = j ( 12 ) = 2 (2 – 1) (3 – 1) = 4 образующих. Элемент a = 2 является образующим, так как 2 6 = 64 = 12 mod 13 ¹ 1, (j ( 13 )/ 2 = 6), 2 4 = 16 = 3 mod 13 ¹ 1, (j ( 13 )/ 3 = 4).
Образующие элементы – 2, 6, 7, 11:
b 0 = 2 1 mod 13 = 2
b 1 = 2 5 mod 13 = 32 mod 13 = 6
b 2 = 2 7 mod 13 = 128 mod 13 = 11
b 3 = 2 11 mod 13 = 2048 mod 13 = 7.
Если некоторое подмножество H множества G само образует группу относительно операции *, определенной в G, то (H, *) называется подгруппой группы (G, *).
Например, подмножество четных целых чисел есть подгруппа аддитивной группы Z всех целых чисел, а подмножество нечетных чисел не будет подгруппой этой группы (сложение на Z не задает операцию на этом подмножестве, так как сумма двух нечетных чисел есть число четное).
Утверждение. Для того чтобы подмножество H образовывало подгруппу группы (G, *), необходимо и достаточно, чтобы выполнялись два условия:
1. Результат операции * (определенной в G) над любыми двумя элементами h 1, h 2 из подмножества H также является элементом из H (h 1* h 2 Î H).
2. Если h Î H, то и обратный к нему элемент h –1 принадлежит H (h –1 Î H).
Наиболее просты так называемые циклические подгруппы, которыми обладает любая группа G. Со всяким элементом a Î G можно связать «порожденную» им циклическую подгруппу, которая, по существу представляет собой наименьшую из подгрупп, содержащую данный элемент.
Введем понятие степени a i элемента a, полагая a i = a i – 1 * a, a 0 = e.
При таком определении степени выполняются правила действий со степенями: для любых целых чисел k и m
a k * a m = a k + m , (a k ) m = a k m , a – k = (a – 1 ) k .
Поскольку операция возведения элемента группы в степень не выводит за пределы группы, то все степени элемента принадлежат некоторой подгруппе группы.
Утверждение. Пусть группа (G, *) содержит элемент a. Тогда все степени a i элемента a образуют циклическую подгруппу, порождаемую элементом a.
Определение. Наименьшая степень t, при которой a t = e называется порядком элемента a группы (G, *), ord (a) = t.
Утверждение. Циклическая подгруппа, порожденная элементом a порядка t, имеет порядок t.
Утверждение. Порядок любого элемента группы делит порядок группы.
Утверждение. (Теорема Лагранжа) Порядок любой подгруппы конечной группы является делителем порядка группы.
Утверджение. Если ord (a) = t, то элемент a k имеет порядок, равный t / НОД (t, k).
Пример. В группе Z 29 * ord (24) = 14, 24 10 = 20, ord (20) = 14 / НОД (14, 10) = 7.
Утверждение. Если (G, *) – циклическая группа порядка n, d – делитель n, то группа (G, *) имеет ровно j (d) элементов порядка d.
Пример. Порядок группы Z 29 * равен 28, d =14 – делитель порядка группы. Группа Z 29 * имеет j (d) = j ( 14 ) = 6элементов порядка 14: 4, 5, 6, 9, 13, 22.
Определение. Две группы (A, *) и (G, ·) называются изоморфными, если существует взаимно однозначное соответствие f: A ® G между элементами множеств A и G, сохраняющее действие операций: для любых элементов a, b Î A выполняется равенство f (a * b) = f (a) · f (b) Î G.
Пример. Мультипликативная группа положительных вещественных чисел – (R+, ´). Аддитивная группа вещественных чисел – (R, +). Взаимно однозначное соответствие – log: R+ ® R сохраняет действие операций в группах: log (x y) = log (x) + log (y). Следовательно, группы (R+, ´) и (R, +) являются изоморфными.
1. Дайте определение группы.
2. Дайте определение порядка группы.
3. Что такое порядок элемента группы?
4. Какая группа называется коммутативной?
5. Дайте определение циклической группы.
6. Дайте определение подгруппы.
7. Дайте определение циклической подгруппы.
8. Какой элемент группы называется образующим?
9. Каковы свойства образующих элементов группы Z n * ?
10. Сформулируйте теорему Лагранжа.
11. Какие группы называются изоморфными?
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: