Теория чисел (пилотный поток) 2022/23

О курсе

Этот курс основ теории чисел, который содержит такие базовые разделы как алгоритм Евклида, цепные дроби, арифметические функции, теория сравнений, квадратичные вычеты, первообразные корни. Параллельно будет происходить знакомство с задачами математической криптографии и простейшими криптографическими протоколами.

Предварительная программа

1. Алгоритмы и их сложность. Классические алгоритмы целочисленной арифметики. Быстрый алгоритм возведения в степень.
2. Алгоритм Евклида и его варианты. Теорема Ламе. Расширенный алгоритм Евклида.
3. Конечные цепные дроби. Свойства подходящих дробей.
4. Бесконечные цепные дроби. Однозначность представления действительных чисел цепными дробями. Теорема Лагранжа.
5. Теория сравнений. Кольцо вычетов. Группа обратимых кольца вычетов. Теорема Вильсона. Функция Эйлера. Теоремы Ферма и Эйлера. [Простейшие детерминированные и вероятностные тесты на простоту. Псевдопростые, абсолютно псевдопростые и сильно псевдопростые числа. Понятие о криптографии с открытым ключом. Система шифрования RSA. Криптосистема Эль-Гамаля.]
6. Китайская теорема об остатках. Решение систем линейных сравнений. Решение полиномиальных сравнений. [Криптосистема Рабина и её модификации. ]
7. Квадратичные вычеты. Свойства символов Лежандра и Якоби. Квадратичный закон взаимности. [Тест Соловея--Штрассена. Псевдопростые числа Эйлера. Протоколы, использующие свойства символа Якоби. Генератор Блюм -- Блюма -- Шуба. Криптосистема Блюма -- Гольдвассер. Криптосистема Гольдвассер -- Микали.]
8. Первообразные корни и индексы. Структура группы $\mathbb{Z}^*_m$ для произвольного $m$ [Метод Диффи-Хеллмана. Дискретное логарифмирование. Протоколы аутентификации и "подбрасывание монеты по телефону". Хеш-функция Шаума -- Хайста -- Пфитсман.]
9. Интерполяционный многочлен Лагранжа и его связь с китайской теоремой об остатках. Умножение Карацубы. [Разделение секрета Шамира.]
10. Дискретное преобразование Фурье. Быстрое преобразование Фурье.

Полезные ссылки

Почта для сдачи домашних заданий

Канал в telegram для объявлений: Чат в telegram для обсуждений: Ссылка на курс в Anytask:

Семинары

221, 222 -- Устинов Алексей Владимирович

223, 224 -- Калмынин Александр Борисович

Ассистенты

221 Свирщевский Юрий

222 Шевченко Пётр

223 Кучерявый Пётр

224 Пичушкин Антон

Лекции

Лекция 1 (13.01.2023) Алгоритм Евклида. Теорема Ламе. Расширенный алгоритм Евклида.

Семинары

Семинар 1 Семинар 2

Домашние задания

ДЗ-1 ДЗ-2

Контрольная работа

Будет проведена одна контрольная работа (ориентировочно) после 6-го занятия.

Оценка

Итог = min(10, Округление(0.25 * ДЗ + 0.25 * КР + 0.5 * Э)), где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен. Округление арифметическое.

Книги

Основная литература

1. Акритас А.Г. Основы компьютерной алгебры с приложениями. 1994
2. Алфутова Н. Б., Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. М.: МЦНМО, 2018
3. Бухштаб А. А., Теория чисел
4. Виноградов И. М., Основы теории чисел.
5. Ноден П., Китте К. Алгебраическая алгоритмика
6. Menezes A., Oorschot P. van, Vanstone S. Handbook of Applied Cryptography

Дополнительная литература

1. Василенко, О. Н. Теоретико-числовые методы в криптографии МЦНМО, 2003
2. Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012
3. Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011
4. Кнут, Д. Е. Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы ``Вильямс , М., Санкт-Петербург, Киев, 2000, 724
5. Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001.
6. Ноден, П., Китте, К. Алгебраическая алгоритмика. Изд-во Мир, Москва, 1999
7. Ященко, В. В. (Ed.) Введение в криптографию, МЦНМО, Москва, 1999
8. Hoffstein, J.; Pipher, J., Silverman, J. H. An introduction to mathematical cryptography Springer, 2008,