algebra (1014201)

Файл №1014201 algebra (Алгебраические основы криптологии (из книги В.М.Фомичева))algebra (1014201)2017-06-17СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

- 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. Множество Zm целых неотрицательных вычетов по модулю т образует группу относительно сложения,

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

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

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

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

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

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

(1)

(2)

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

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

является отношением эквивалентности. Классы эквивалентности по отношению к RH называются левыми смежными классами группы 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≤rd . Тогда

,

что противоречит минимальности 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-ой степени . Ее подгруппы называются группами подстановок.

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

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

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

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

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

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

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

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

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

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

Кольца и поля

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

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

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

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

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

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

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

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

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

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

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

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

Тип файла
Документ
Размер
236,5 Kb
Тип материала
Высшее учебное заведение

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

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

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

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

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

Алгебраические основы криптологии (из книги В.М
Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6489
Авторов
на СтудИзбе
303
Средний доход
с одного платного файла
Обучение Подробнее