3.2.2. Подгруппы групп
Подмножество H группы G называется подгруппой этой группы, если H образует группу относительно операции группы G.
Подгруппы группы G, отличные от тривиальных подгрупп {e}G, называются собственными подгруппами.
Теорема 3.2.1. Подмножество Н группы G будет ее подгруппой тогда и только тогда, когда выполняются условия:
-
a, b Н =>ab H;
-
a Н =>a-1 H.
Теорема 3.2.2. Если Н – подгруппа группы G, то отношение RH на G, определяемое условием
(а, b) RH <=>а = bh для некоторого h H,
является бинарным отношением эквивалентности.
Классы эквивалентности по отношению RH называются левыми смежными классами группы G по подгруппе Н и обозначаются
аН ={аh| hH}.
Смежные классы группы по подгруппе либо совпадают, либо не пересекаются. Аналогично определяются правые смежные классы по подгруппе Н, которые имеют вид Нa ={ha | h Н}. Для абелевой группы эти два понятия идентичны.
Пусть, например, G = Z, Н = 2Z – подгруппа четных чисел. Тогда имеем два смежных класса: 2Z – четные числа, 1 + 2Z — нечетные.
Теорема 3.2.3. Если Н – конечная группа, то каждый (левый или правый) смежный класс по ней содержит |Н| элементов.
Теорема 3.2.4. Пусть G – конечная группа. Тогда
|G|=[G:H] |Н|.
Следствие 3.2.1. (Лагранж). Порядок конечной группы делится на порядок любой ее подгруппы.
Пусть а G. Положим ап =ааа, если п — натуральное, ап =(а-1)-п, если п – целое отрицательное, и, наконец, а0 = е. Таким образом можно рассмотреть подмножество
a = { ап| nZ}.
Оно, как легко показать, является подгруппой группы G. Эта подгруппа называется циклической подгруппой, порожденной элементом а. Ее порядок называется порядком элемента а. Иными словами, элемент а G называется элементом порядка т N, если ат = е, где т – наименьшее натуральное с этим условием. Легко показать, что т|l, если аl = е. Если такого т нет, то элемент а называется элементом бесконечного порядка. Из теоремы Лагранжа вытекает, что порядок конечной группы G делится на порядок любого ее элемента а. Поэтому aG = е. Поскольку |Z*m|= (т), то в качестве еще одного следствия получается теорема Эйлера о том, что если (а,т) =1, то
а(m) 1(mod m).
В дальнейшем нам потребуется утверждение о порядках элементов в абелевой группе G. Пусть a,bG и их порядки т и п соответственно, причем (m,п) = 1. Покажем, что порядок произведения аb равен тп. Обозначим порядок ab через . Тогда (аb), а значит, (аb)m =1 => ambm=1 => bm=1 => п|т => n|. Аналогично показывается, что т|. Поэтому тп|. Последнее, в силу минимальности , означает = тп. Доказанное является частным случаем следующего утверждения.
Теорема 3.2.5. Пусть даны два элемента a,bG абелевой группы. Тогда в группе найдется элемент порядка [т, п].
- Криптографическая защита информации
- Оглавление
- Раздел 1. Общие подходы к криптографической защите информации
- Тема 1. Теоретические основы криптографии
- 1.1. Криптография
- 1.2. Управление секретными ключами
- 1.3. Инфраструктура открытых ключей.
- 1.4. Формальные модели шифров
- 1.5. Модели открытых текстов
- Тема 2. Простейшие и исторические шифры и их анализ
- Тема 3. Математические основы криптографии
- 3.1. Элементы алгебры и теории чисел
- 3.1.1. Модулярная арифметика. Основные определения.
- 3.1.2. Алгоритм Евклида нахождения наибольшего общего делителя
- 3.1.3. Взаимно простые числа
- 3.1.4. Наименьшее общее кратное
- 3.1.5. Простые числа
- 3.1.6. Сравнения
- 3.1.7. Классы вычетов
- 3.1.8. Функция Эйлера
- 3.1.9. Сравнения первой степени
- 3.1.10. Система сравнений первой степени
- 3.1.11. Первообразные корни
- 3.1.12. Индексы по модулям рk и 2рk
- 3.1.13. Символ Лежандра
- 3.1.14. Квадратичный закон взаимности
- 3.1.15. Символ Якоби
- 3.1.16. Цепные дроби
- 3.1.17. Подходящие дроби
- 3.1.18. Подходящие дроби в качестве наилучших приближений
- 3.2. Группы
- 3.2.1. Понятие группы
- 3.2.2. Подгруппы групп
- 3.2.3. Циклические группы
- 3.2.4. Гомоморфизмы групп
- 3.2.5. Группы подстановок
- 3.2.6. Действие группы на множестве
- 3.3. Кольца и поля
- 3.3.1. Определения
- 3.3.2. Подкольца
- 3.3.3. Гомоморфизмы колец
- 3.3.4. Евклидовы кольца
- 3.3.5. Простые и максимальные идеалы
- 3.3.6. Конечные расширения полей
- 3.3.7. Поле разложения
- 3.3.8. Конечные поля
- 3.3.9. Порядки неприводимых многочленов
- 3.3.10. Линейные рекуррентные последовательности
- 3.3.11. Последовательности максимального периода
- 3.3.12. Задания
- Тема 4. Классификация шифров
- 4.1. Классификация шифров по типу преобразования
- 4.2. Классификация шифров замены
- 4.3 Шифры перестановки
- 4.3.1. Маршрутные перестановки
- 4.3.2. Элементы криптоанализа шифров перестановки
- 4.4. Шифры замены
- 4.4.1. Поточные шифры простой замены
- 4.4.2. Криптоанализ поточного шифра простой замены
- 4.4.3. Блочные шифры простой замены
- 4.4.4. Многоалфавитные шифры замены
- 4.4.5. Дисковые многоалфавитные шифры замены
- 4.5. Шифры гаммирования
- 4.5.1. Табличное гаммирование
- 4.5.2. О возможности восстановления вероятностей знаков гаммы
- 4.5.3. Восстановление текстов, зашифрованных неравновероятной гаммой
- 5.5.4. Повторное использование гаммы
- 4.5.5. Криптоанализ шифра Виженера
- Тема 5. Поточные шифры
- 5.1. Принципы построения поточных шифрсистем
- Примеры поточных шифрсистем
- 5.3. Линейные регистры сдвига
- 5.4. Алгоритм Берлекемпа-Месси
- 5.5. Усложнение линейных рекуррентных последовательностей
- 5.6. Методы анализа поточных шифров
- 6. Блочные шифры
- 6.1. Принципы построения блочных шифров
- 6.2. Примеры блочных шифров
- 6.3. Режимы использования блочных шифров
- 6.4. Комбинирование алгоритмов блочного шифрования
- 6.5. Методы анализа алгоритмов блочного шифрования
- 6.6. Рекомендации по использованию алгоритмов блочного шифрования
- 7. Криптографические хэш-функции
- 7.1. Функции хэширования и целостность данных
- 7.2. Ключевые функции хэширования
- 7.3. Бесключевые функции хэширования
- 7.4. Целостность данных и аутентификация сообщений
- 7.5. Возможные атаки на функции хэширования
- Тема 8. Криптосистемы с открытым ключом
- 8.1. Шифрсистема rsa
- 8.2. Шифрсистема Эль-Гамаля
- 8.3. Шифрсистема Мак-Элиса
- 8.4. Шифрсистемы на основе "проблемы рюкзака"