Алгебраические структуры (SE)

Программа курса

1. Операции, структуры. Моноиды. Группы. Числовые группы, свободные группы, симметрические группы и группы автоморфизмов графов.
2. Подгруппы, классы смежности. Лемма о разбиениях на классы смежности, теорема Лагранжа. Порядок элемента. Лемма о порядке элемента.
3. Циклические группы. Теорема об описании циклических групп. Дискретный логарифм. Две теоремы о подгруппах циклической группы.
4. Прямое произведение групп. Теорема о прямом произведении. Теорема о разложении конечной циклической группы в прямое произведение.
5. Кольца, подкольца, прямое произведение колец. Числовые кольца, кольца многочленов. Области целостности. Поля. Неприводимые элементы.
6. Делимость. Евклидовы области. Соотношение и коэффициенты Безу. Алгоритм Евклида. Теорема об алгоритме Евклида и следствие из нее.
7. Китайская теорема об остатках и ее формулировка в терминах сравнений. Функция Эйлера. Теорема Эйлера. Теорема о функции Эйлера.
8. Лемма о корнях многочлена, теорема о цикличности. Теорема о группах обратимых остатков. Критерий существования дискретного логарифма.
9. Степенные уравнения в группах. Тесты Ферма, Эйлера и Миллера–Рабина. Числа Кармайкла. Протокол Диффи–Хеллмана. Алгоритм RSA.
10. Теорема о разложении перестановки в произведение транспозиций. Связь с алгоритмами сортировки массива. Знак, знакопеременные группы.