Алгебра в криптографии
Объявление: Выставлены итоговые оценки (вкладка Накоп). Жалобы на арифметические ошибки принимаются до 28 декабря.
Оценки и критерии оценивания домашнего задания
Материалы к лекциям и семинарам
Плейлист с видеозаписями лекций
О чём этот курс: В современной криптографии, например, в алгоритме Ривеста-Шамира-Адлемана (RSA) или в протоколе Диффи-Хеллмана на эллиптических кривых (ECDH), используются абстрактные алгебраические понятия, которые изначально возникли в связи с задачами чистой математики (главным образом задачами теории чисел и алгебраической геометрии). Одним из таких понятий является понятие делимости, и связанные с ним задачи: поиск наибольшего общего делителя, разложение на простые множители, доказательство однозначности разложения, решение диофантовых уравнений и т.п. Эти задачи выглядят конкретными (хотя и не всегда простыми), когда речь идёт о делимости целых чисел, но если целые числа заменить на более общие числа (например, на числа вида a+b\sqrt2 или вида a+bi, где a и b целые), на многочлены (от одной или нескольких переменных) или на степенные ряды, то возникает потребность абстрагироваться от деталей, чтобы уловить суть. Цель курса – разобраться в конкретных приложениях алгебры в криптографии на математическом, а не на инженерном уровне.
Программа:
- Разложение на множители целых чисел и многочленов. Делимость в кольцах. Степенные ряды и гауссовы целые числа.
- Алгоритм Евклида для целых чисел и многочленов. Евклидовы и неевклидовы кольца. Основная теорема арифметики. Кольца целых квадратичных числовых полей.
- Китайская теорема об остатках. Алгоритм RSA. Поиск больших простых чисел, тесты на простоту. Алгоритмы разложения на множители чисел и многочленов.
- Коники и кубики. Проективные замены координат. Приведение коник и кубик к каноническому виду.
- Рациональная параметризация коники. Сложение точек на кубике. Метод секущих и решение диофантовых уравнений.
- Конечные поля. Коники и кубики над конечными полями. Протокол Диффи-Хеллмана на эллиптических кривых.
Рекомендуемая литература:
- И.М. Гельфанд и А.Шень, Алгебра
- А.Л. Городенцев, Вышкинская алгебра
- J.A. Gallian, Contemporary Abstract Algebra (пишите лектору, если нужна копия)
- В.А. Острик, М.А. Цфасман, Алгебраическая геометрия и теория чисел
Формула оценки: 30% ДЗ + 30% К + 40% Э + 10% C, где ДЗ – средняя оценка за домашние задания, К – оценка за контрольную в конце 1-го модуля, Э – оценка за письменный экзамен, С – оценка за работу на семинарах. При вычислении итоговой оценки вторая цифра после запятой не учитывается, оценка округляется в большую сторону, например, 9.1 округляется до 10.