Алгебра

Специалитет 2020/2021

Статус: Курс обязательный (Компьютерная безопасность)

Кто читает: Департамент прикладной математики

Где читается: Московский институт электроники и математики им. А.Н. Тихонова

Когда читается: 2-й курс, 1, 2 модуль

Формат изучения: без онлайн-курса

Преподаватели: Анашкин Александр Владимирович, Рожков Михаил Иванович

Специальность: 10.05.01. Компьютерная безопасность

Язык: русский

Кредиты: 3

Контактные часы: 56

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

Настоящая дисциплина относится к циклу математических и естественно-научных дисциплин и блоку дисциплин, обеспечивающих базовую подготовку. Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями: школьными знаниями и компетенциями, основными понятиями линейной алгебры и теории множеств. Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин: криптографические методы защиты информации, криптографические протоколы, теоретико-числовые методы в криптографии. Дисциплина реализуется в он-лайн формате

Цель освоения дисциплины

Применение соответствующего математического аппарата для формализации, анализа и решения проблем, возникающих в ходе профессиональной деятельности
Решение систем линейных уравнений над полем и кольцом вычетов
Проведение эффективных вычислений в кольцах вычетов и кольцах многочленов

Планируемые результаты обучения

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

Содержание учебной дисциплины

Группа, подгруппа, нормальный делитель, факторгруппа. Примеры на основе групп (Z,+), (Zn,+), (Zn*,∙), Sn.
Порядок элемента группы, циклическая группа, описание множества образующих элементов циклической группы (Zn,+).
Гомоморфизм групп, ядро гомоморфизма. Примеры на основе групп (Z,+), (Zn,+), (Zn*,∙), Sn.
Характеры групп
Внешнее и внутреннее прямое произведение (сумма) групп. Примеры на основе групп (Z,+), (Zn,+), (Zn*,∙), Sn.
Кольцо, подкольцо, идеал, фактор-кольцо. Примеры на основе колец Z, Zn, F[x], F[x]/f(x).
Характеристика кольца, делители нуля, обратимые элементы. Примеры на основе колец Z, Zn, F[x], F[x]/f(x).
Гомоморфизм и изоморфизм колец. Примеры на основе колец Z, Zn, F[x], F[x]/f(x).
Кольцо многочленов F[x] над полем F
Кольцо многочленов F[x] над полем F, деление с остатком, формула для остатка от деления многочлена f(x) на одночлен (x-a), критерий отсутствия кратных корней у многочлена над полем, оценка числа различных корней.
Кольцо многочленов F[x]/f(x) над полем F по модулю заданного многочлена f(x), критерий отсутствия в данном кольце делителей нуля.
Критерий мультипликативной обратимости и методы нахождения обратного элемента для колец Zn и F[x]/f(x)
Неприводимые многочлены
Неприводимые многочлены, критерий неприводимости для многочленов степени ≤ 3, описание всех неприводимых многочленов степени ≤ 3 над полем из двух элементов.
Идеалы колец K{Z, Zn, F[x], F[x]/f(x)}.
Идеалы колец K{Z, Zn, F[x], F[x]/f(x)}. Доказательство того, что каждый идеал этих колец является главным идеалом. Критерий совпадения идеала J=a∙K с кольцом K.
Критерий максимальности идеалов J=a∙K
Китайская теорема об остатках для чисел и многочленов.
Условия разложимости кольца K{Zn, F[x]/f(x)} в прямую сумму колец.
Методы решения уравнений
Методы решения уравнений (оценки числа решений) и нахождения мультипликативных порядков элементов в кольце K{Zn, F[x]/f(x)} (критерий наличия решений уравнения ax=b, оценка числа решений данного уравнения, связь с решениями уравнения ax=0).
Отношение эквивалентности, смежные классы по подгруппе как классы эквивалентности. Примеры на основе групп (Z,+), (Zn,+), (Zn*,∙), Sn.
Основные понятия и свойства теории конечных полей.
Описание конечного поля GF(q) как поля разложения многочлена xq-x=0.
Описание подполей конечного поля GF(q).
Алгебраические элементы поля над заданным подполем. Минимальный многочлен алгебраического элемента и его свойства.
Поле разложения неприводимого многочлена над конечным полем.
Примитивные элементы конечного поля
теорема существования, число примитивных элементов, описание всех примитивных элементов через степени одного из них, алгоритмы проверки примитивности элементов поля, примеры на основе полей Zp и F[x]/f(x)
Функция след и ее свойства
Квадратичные вычеты и невычеты в поле Zp
описание через степени примитивного элемента, доказательство равномощности множеств вычетов и невычетов
Символы Лежандра и Якоби, формула Эйлера
использование для проверки неприводимости квадратного многочлена над полем Zp
Период многочлена над конечным полем. Методы нахождения периода многочлена, многочлены максимального периода.
Методы нахождения корней многочленов над полем Zp.

Элементы контроля

Самостоятельная работа 1
Самостоятельная работа 2
Самостоятельная работа 3
Самостоятельная работа 4

Промежуточная аттестация

Промежуточная аттестация (2 модуль)
0.5 * Итоговая аттестация + 0.5 * Контрольная работа 1

Программа дисциплины