Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

- 16 -

АЛГЕБРАИЧЕСКИЕ ОСНОВЫ КРИПТОЛОГИИ

ИЗ КНИГИ

В.М.ФОМИН

«ДИСКРЕТНАЯ МАТЕМАТИКА И КРИПТОЛОГИЯ»

Операции, полугруппы, группы 2

Кольца и поля 9

Векторные пространства 11

Конечные расширения полей 13

Операции, полугруппы, группы

Внутренней бинарной операцией, заданной на непустом множе­стве X, называется отображение .Если то также и . Часто операцию т обозначают некоторым символом, на­пример: +, •, и др.; вместо пишут а b.

Внутренняя бинарная операция (для краткости будем называть ее операцией), заданная на множестве X, называется:

1) ассоциативной, если для любых

2) коммутативной, если для любых

Элемент е множества X называется нейтральным (или единич­ным) относительно операции , если для любого элемента

а е = е а = а.

Множество X с заданной на нем ассоциативной операцией назы­вается полугруппой. Полугруппу с единичным элементом часто на­зывают моноидом (или просто полугруппой с единицей).

Примером моноида является множество всех преобразований множества X, где единица - это тождественное преобразование. В моноиде имеется лишь один единичный элемент. Действительно, если е' - другая единица моноида, то

е'= е' е = е.

Подмножество X' множества X называется замкнутым относи­тельно операции , если для любых .

Подмножество X' полугруппы X называется подполугруппой, ес­ли X' замкнуто относительно операции .

Элемент а моноида X называется обратимым, если найдется эле­мент , для которого

а b = b а = е;

такие элементы а u b называются взаимно-обратными.

Группой называется моноид G, все элементы которого обратимы. Иными словами, множество G называется группой, если на нем зада­на ассоциативная операция , относительно которой в G имеется еди­ница и для каждого элемента имеется обратный элемент.

Если операция коммутативна, то группа называется абелевой или коммутативной.

Для любого элемента группы G имеется лишь один обратный. Действительно, если х u у- обратные элементы для , то, исполь­зуя ассоциативность операции, имеем:

х = х е = х (а у)=(х а) у = е у = у.

Число элементов конечной группы (полугруппы) G называется порядком группы (полугруппы) G и обозначается символом .

Примеры групп:

1. Множество Z целых чисел образует группу относительно сло­жения.

2. Множество Z_m целых неотрицательных вычетов по модулю т образует группу относительно сложения,

1. Множество Z_m* целых неотрицательных вычетов по модулю т, взаимно простых с т, образует группу относительно умножения. Поря­док группы Z_m* обозначаемый φ(m), называется функцией Эйлера.

1. Множество S_n всех подстановок степени п образует группу относительно произведения и называется симметрической группой n-й степени, \S_n\=n!.

В зависимости от рассматриваемой групповой операции (сложе­ние или умножение) группу называют аддитивной или мультипли­кативной.

Подмножество Н группы G называется подгруппой этой группы, если Н образует группу относительно операции группы G.

Подгруппы группы G, отличные от тривиальных подгрупп {е} и G группы G, называются собственными подгруппами.

Теорема 2.1. Подмножество H группы G является подгруппой то­гда и только тогда, когда выполняются следующие условия:

(1)

(2)

Доказательство. Необходимость следует из определения группы. Докажем достаточность. Первое условие означает, что групповая операция является внутренней операцией и для подмножества Н. Второе условие означает наличие обратного элемента для каждого элемента подмножества Н. Ассоциативность в Н имеется, так как она имеет место в более широком множестве G. Единица группы G явля­ется и единицей подгруппы Н, так как Н есть подмножество G.

Условия (1) и (2) теоремы 2.1 равносильны условию: если , то . Если Н - подгруппа группы G, то бинарное отношение R_H на G, определяемое условием

является отношением эквивалентности. Классы эквивалентности по отношению к R_H называются левыми смежными классами группы G по подгруппе Н и обозначаются символами

Аналогичным образом определяются правые смежные классы Н а по подгруппе Н, которые имеют вид

.Для абелевой группы левые и правые смежные классы совпадают. Если Н - конечная группа, то каждый смежный класс содержит по элементов.

Если число смежных классов группы G по подгруппе Н конечно, то это число называется индексом подгруппы Н в группе G и обо­значается [G:H]. В этом случае справедливо так называемое раз­ложение группы по подгруппе:

где справа все смежные классы есть блоки разбиения и p = [G:H]-1.

Отсюда следует теорема.

Теорема 2.2. Пусть G - конечная группа. Тогда

Следствие (Лагранж). Порядок конечной группы делится на по­рядок любой ее подгруппы.

Пусть . Для n>0 положим . Если n-отрицательное, то под понимается произведение .

Рассмотрим подмножество группы G, где . Легко показать, что группа есть подгруппа группы G. Она называется циклической подгруппой, порожденной элементом а, а ее порядок называется порядком элемента а. Иначе говоря, элемент а называется элементом порядка m, если , где m - наименьшее натуральное с таким условием. Отсюда следует, что порядок конечной группы делится на порядок любого ее элемента и, следовательно,

.

Так как , то из последнего равенства вытекает, в частности, теорема Эйлера: при (a,m)=1 выполнено

Теорема 2.3. Если элементы a и b абелевой группы G имеют порядки n и m соответственно, то в G найдется элемент порядка HOK(n,m).

Доказательство. Если (n,m)=1, то искомым элементом является a*b. Если (n,m)=d, то элементы имеют порядки n/d и m соответственно и их произведение имеет порядок HOK(n,m).

Мультипликационная группа G называется циклической, если она порождена одним элементом, то есть в G имеется элемент а (называемый образующим) такой, что любой другой элемент b из G представим в виде , n-целое. В таком случае G= . Циклическая группа является абелевой.

Теорема 2.4. Всякая подгруппа циклической группы также является абелевой.

Доказательство. Пусть H-собственная группа циклической группы . Если , то и , поэтому H содержит степень элемента а с натуральным показателем. Обозначим через d наименьшее натуральное число, для которого . Пусть теперь , где n=d*q+r,0≤r≤d . Тогда

,

что противоречит минимальности d, если r ≠ 0.Поэтому r = 0 и H есть циклическая группа .

Теорема 2.5. В конечной циклической группе порядка m элементов порождает подгруппу порядка m/(r,m).

Доказательство. Пусть d=(r,m). Порядок группы равен наименьшему натуральному n такому, что . Это равенство выполняется лишь тогда, когда m делит r*n, то есть тогда и только тогда, когда m/d делит n. Наименьшее натуральное n с таким свойством есть m/d.

Из доказанной теоремы вытекает следующая теорема.

Теорема 2.6. Конечная циклическая группа порядка m содержит φ(x) образующих. Элемент является образующим лишь при условии (r,m)=1.

Отображение группы G в группу называется гомоморфизмом, если оно согласовано с операциями на группах G и , то есть f(a*b)=f(a)*f(b) для любых a,b  G. Если это отображение сюръективно, то оно называется эпиморфизом, при этом группа называется гомоморфным образом группы G. Биективный гомоморфизм называется изоморфизмом (в этом случае обозначается ). Изоморфизм группы на себя называется автоморфизмом.

Рассмотрим симметричную группу n-ой степени . Ее подгруппы называются группами подстановок.

Подстановку на множестве { a₁,a₂,...,a_n} вида a₁ → a₂→…→ a_л→ a₁ называют циклом длины k и обозначают (a₁,a₂,...,a_n).Цикл длины 2 называют транспозицией. Два цикла называются независимыми, если множества, элементов, на которых они определены, не пересекаются.

Каждая подстановка разлагается в произведение:

а)независимых циклов единственным образом;

б)транспозицией.

Подстановка называется четной или нечетной в зависимости от четности числа транспозиций в ее разложении.

Теорема 2.7. (Кэли). Всякая конечная группа G порядка п изо­морфна некоторой подгруппе группы S_n.

Доказательство. Пусть е, g_h ,g₂, .... g_n-1 - все элементы группы G. Для фиксированного элемента а группы G рассмотрим отображение Имеем подстановку

Вместе с тем получаем отображение ,при котором . Убедимся, что это и есть искомый изоморфизм.

Во-первых, это отображение инъективно, так как различным эле­ментам а и b группы G отвечают различные подстановки и (в первом случае , а во втором ).

Во-вторых, это отображение согласовано с операциями, то есть при любых . Действительно,

Кольца и поля

Кольцом называется множество R с двумя внутренними бинар­ными операциями + и , такое, что:

R - абелева группа относительно операции +;

операция умножения ассоциативна;

выполнены законы дистрибутивности, то есть для всех

Нейтральный элемент аддитивной группы кольца называется ну­лем (обозначается 0).

Элемент, обратный по сложению к элементу а, обозначается через (-a).

Примеры колец:

1. Кольцо Z целых чисел.

2. Кольцо Z/т целых неотрицательных вычетов по модулю т.

3. Кольцо многочленов R[x] над кольцом R. Многочлен (или полином) f(x) из R[x] - это выражение вида

где a₀,a₁,...,a_n - элементы кольца R, называемые коэффициентами многочлена f(x), a_n ≠0. Натуральное число п называется степенью многочлена f(х) и обозначается degf(x). Многочлен вида называ­ется одночленом, а≠О, n≥0.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов книги