Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
3. Для любого целого числа п ^ 1 множество целых чисел по модулю п образует конечную аддитивную группу, состоящую из п элементов. Нейтральным элементом этой группы является число 0, причем для любого элемента а выполняется условие а-1 = п — а (свойство 2 теоремы 4.2 из раздела 4.3.2.5). Эта группа обозначается как Z„. Итак, полное обозначение этой группы выглядит следующим образом: (Zn, +(modn)). (Обратите внимание на то, что 7Ln — это сокращение стандартного обозначения Ъ/пЪ. Причина, по которой вводится такое обозначение, будет указана в примере 5.5.)
4. Числа, обозначающие часы на циферблате, образуют группу Ъ\ч по отношению к сложению по модулю 12. Будем называть группу (Z12, +(mod 12)) "часовой группой" ("clock group").
5. Подмножество множества Ъп, содержащее элементы, взаимно простые с числом п (т.е. gcd(a, п) = 1), образует конечную мультипликативную группу. Операция умножения выполняется по модулю п, нейтральный элемент е
1, и для любого элемента а из этой группы обратный элемент а~1 можно вычислить с помощью алгоритма Евклида (алгоритм 4.2). Эта группа обозначается как Z*. Например, (Z*, -(mod 15)) = ({1,2,4,7,8,11,13,14}, ¦ •(mod 15)).
6. Для пары множеств В = {F, Т} обозначим через о операцию © (логическое "исключающее или"): F®F = F,F®T = T®F = T,T®T = F. Тогда пара множеств В относительно операции © является конечной группой, в которой е = F и Г-1 = Т.
7. Корни уравнения х3 — 1 = 0 образуют конечную группу относительно умножения, в которой е—1 (очевидно, что единица является корнем этого уравнения). Обозначим эту группу как Roots(a;3 — 1). Найдем другие элементы группы Roots(x3 — 1), а также обратные к ним элементы. Поскольку х3 — 1 является полиномом третьей степени, он имеет только три корня. Обозначим неизвестные нам корни буквами а и /3. Из соотношения ж3 — — 1 = (х — 1)(х2 + х + 1) следует, что числа а и /3 должны быть корнями уравнения х2 + х + 1 = 0. Используя зависимость между корнями и коэффициентами квадратного уравнения, получаем, что а/3 = 1. Следовательно, а-1 = /3 и /З-1 = а. Читатели могут самостоятельно убедиться, что аксиома замкнутости выполняется (т.е. а2 и /З2 также являются корнями уравнения х3 - 1 = 0). ?
178 Часть II. Математические основы
Определение 5.4 (Сокращенное представление повторяющейся операцм группы). Пусть G — группа с операцией о. Для любого элемента а € G и лкм бого неотрицательного целого числа г € N обозначим через аг EG элемент
ао а о • • - ос
Примечание 5.1.
1. Выражение alEG используется только в качестве сокращенного представ-* ления повторяющейся операции а о а о • • • о а. Следует помнить, что эта
г
"операция " не является операцией группы.
2. Некоторые группы для удобства записываются в аддитивном виде, нам пример (Zn, +(modn)). В этом случае элемент аг означает г • а. ОднакЩ и в этой ситуации следует иметь в виду, что операция ¦ не является операцией группы, а элемент г, как правило, не является элементом группш (например, в группе (Zn, +(modn)) при г> п). ?
Определение 5.5 (Подгруппа). Подгруппой группы G называется непустое поди множество Н множества G, которое само является группой относительно тот же операции, что и группа G. Для того чтобы подчеркнуть, что Н являетст подгруппой группы G, используется запись HC.G. Если Н является собственном подгруппой группы G, используется запись Н С G (т.е. Н ф G).
Пример 5.2 (Группы).
1. Относительно сложения 7L С Q С R С С.
2. Относительно сложения множество четных чисел и нуль образуют подгруп! пу каждой из групп, перечисленных выше.
3. "Часовая группа" (Z12, +(mod 12)) имеет следующие подгруппы: ({0}, + 1 ({0,6}, +), ({0,4,8}, +), ({0,3,6,9}, +), ({0,2,4,6,8,10}, +), (Z12, +).
4. Относительно умножения Q* С R* С С*.
5. Пусть п — нечетное положительное целое число, a Fermat(n) — подмноже-1 ство множества Z* такое, что любой элемент а Е Fermat(n) удовлетворяв!
п-1
условию а 2 = ±1 mod п. Тогда
Fermat(n) С Z*.
Более того, если число п — целое, то по малой теореме Ферма (теорема 6.11 в разделе 6.4) Fermat(n) = Z*, в противном случае Fermat(n) являете! собственной подгруппой группы Z*.
Глава 5. Алгебраические основы
179
6. В примере 5.1.6 множество {F} является собственной подгруппой группы В. Однако множество {Г} не является подгруппой группы В, поскольку не содержит нейтрального элемента (т.е. нарушается аксиома тождества).
7. (См. пример 4.1.) Полиномиальный язык DIV3 является подгруппой группы Ъ.
8. Множество {е} является подгруппой любой группы. ?
Определение 5.6 (Порядок группы). Порядком #G конечной группы G называется количество ее элементов.
Пример 5.3 (Группы).
1. #Ъп = п.
2. В примере 5.1.6 #В = 2.
3. В примере 5.1.7 # Roots(z3 - 1) = 3. ?
5.2.1 Теорема Лагранжа
Рассмотрим одну из замечательных теорем теории групп. Определение 5.7 (Смежный класс). Пусть G — абелева группа и Н С G. При
def
a EG множество а о Н = {aoh\hE Н} называется левым смежным классом (coset) подгруппы Н.
Теорема 5.1 (Теорема Лагранжа). Если Н — подгруппа группы G, то #Я | #G, т.е. число #Н является делителем числа #G.
