Теория чисел (основной поток) 2023/24

О курсе

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

Преподаватели и учебные ассистенты

Группы	БПМИ235	БПМИ236	БПМИ237	БПМИ238	БПМИ239	БПМИ2310	БПМИ2311	БПМИ2312
Лектор	О.Н. Герман
Семинаристы	О.Н. Герман	А.В. Устинов	А. Калмынин		М. Чанга	Д. Фроленков	А. Радомский
Ассистенты	Герасимов Борис	Смирнова Валерия	Лавицкая Александра	Потарусов Артём	Воронко Алексей	Грецкая Вера	Кокоева Мария	Михнёнок Екатерина
Ассистент лектора	Агаев Мурад

Правила выставления оценок

В домашнем задании каждая задача оценивается в 10 баллов. Оценка за каждое ДЗ получается усреднением оценок за задачи, в него входящие (без округления). Итоговая оценка за ДЗ получается усреднением оценок по всем ДЗ (без округления). Округление происходит только в конце при вычислении итоговой оценки за курс.

Правила сдачи заданий

Всё должно быть написано аккуратно и понятно.

У Вас есть возможность отправить домашнее задание после истечения срока сдачи дважды в течение 24 часов. Однако этот шанс не может быть использован для сдачи последнего домашнего задания.

Лекции

Лекция 1 (12.01.2024): Деление с остатком, алгоритм Евклида, представление НОД двух чисел в виде их линейной комбинации с целыми коэффициентами, Важная лемма.

Лекция 2 (19.01.2024): Теорема Ламе, основная теорема арифметики, линейные диофантовы уравнения от двух неизвестных, конечные цепные дроби.

Лекция 3 (26.01.2024): Арифметические функции, суммы по делителям и мультипликативность, функция Мёбиуса, формула обращения Мёбиуса, явная формула для функции Эйлера.

Лекция 4 (02.02.2024): Сравнения по модулю, классы вычетов, критерий обратимости вычета по умножению, теорема Вильсона, теорема о полной и приведённой системах вычетов, теорема Эйлера, малая теорема Ферма.

Лекция 5 (09.02.2024): Криптографическая система RSA, понятие решения полиномиального сравнения, китайская теорема об остатках.

Лекция 6 (16.02.2024): Количество решений полиномиального сравнения по простому модулю, критерий Эйлера квадратичности вычета, символ Лежандра и его элементарные свойства.

Лекция 7 (24.02.2024): Лемма Гаусса о символе Лежандра, вывод формулы для символа Лежандра от двойки, доказательство квадратичного закона взаимности Гаусса.

Лекция 8 (01.03.2024): Символ Якоби и его свойства, тест Соловея-Штрассена.

Лекция 9 (09.03.2024): Доказательство теоремы о тесте Соловея-Штрассена, определение показателя вычета по модулю, делимость значения функции Эйлера на показатель, теорема о количестве первообразных корней в приведённой системе вычетов.

Лекция 10 (15.03.2024): Доказательство существования первообразных корней по простому модулю, протокол Диффи-Хеллмана построения общего ключа шифрования, криптографическая система Эль-Гамаля.

Конспект лекций

Семинары

Семинар 1

Семинар 2

Семинар 3

Семинар 4

Семинар 5

Семинар 6

Семинар 7

Семинар 8

Семинар 9

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

ДЗ 1

ДЗ 2

ДЗ 3

ДЗ 4

ДЗ 5

ДЗ 6

ДЗ 7

ДЗ 8

ДЗ 9

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

Контрольная работа будет проведена 2 марта (в субботу) в 09:30, длительность - полтора часа. Разрешается использование (кнопочного) калькулятора. Разрешается принести с собой лист формата А4 с выписанными формулами (не с распечатками лекций, а с отдельными формулами)

Распределение по аудиториям

R201 - БПМИ236, БПМИ239

R401 - БПМИ2311, БПМИ2310, БПМИ235

R404 - БПМИ2312, БПМИ237, БПМИ238

Контрольная работа - демо-версия

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

Ссылка для тех, кто будет онлайн сдавать.

Коллоквиум

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

Коллоквиум проходит в виде беседы принимающего со студентом, в которой студент отвечает на вопросы билета, а принимающий имеет возможность задавать любые уточняющие вопросы в рамках билета. На подготовку билета студенту даётся 40 минут.

Билет будет состоять из следующих частей:

1. два определения (по 1 баллу каждое);
2. формулировки двух теорем без доказательства (по 1 баллу каждая);
3. две теоремы с доказательствами (по 2.5 балла каждое).

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

Всего за билет студент может получить до 9 баллов. После этого проверяющий задаёт дополнительный вопрос по программе курса. Ответ на дополнительный вопрос оценивается в 2 балла. Итоговая оценка равна минимуму из 10 и набранного числа баллов.

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

Cсылка для тех, кто будет онлайн сдавать. Начало 14:00.

Расписание коллоквиума

Группа	Время	аудитория
БПМИ235	9:30	R407
БПМИ236	16:00	M303
БПМИ237	13:00	R405
БПМИ238	16:00	M203
БПМИ239	14:00	R407
БПМИ2310	17:30	M303
БПМИ2311	17:30	M203
БПМИ2312	14:00	R405

Экзамен

Экзамен будет проведен 29 марта (в пятницу) в 11:00 в письменном формате. Длительность - два часа. Разрешается использование (кнопочного) калькулятора. Разрешается принести с собой лист формата А4 с выписанными формулами (не с распечатками лекций, а с отдельными формулами)

Распределение по аудиториям

R201 - БПМИ235, БПМИ236, БПМИ237, БПМИ238

R301 - БПМИ239, БПМИ2310, БПМИ2311, БПМИ2312

Cсылка для тех, кто будет онлайн сдавать.

Демо-вариант

Оценка

В течение года установлены следующие формы контроля:

• один письменный экзамен (ЭК), в сессию после модуля;
• одна письменная контрольная работа (KР), которую планируется провести в середине 3-го модуля;
• один коллоквиум (KЛ), который планируется провести в конце 3-го модуля;
• около 10 домашних заданий (ДЗ, где ДЗ --- есть среднее арифметическое оценок всех домашних работ); обычно домашнее задание выдается к каждому семинару.

Накопленная Оценка, НО, вычисляется без округления по следующей формуле: НО = 0.4 * ДЗ + 0.2 * Кр + 0.4 * КЛ. Итоговая Оценка за Курс, ИО, вычисляется по следующей формуле: ИО = Округление(7/10*НО + 3/10*ЭК),

где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, ЭК — оценка за экзамен, КЛ ¬– оценка за коллоквиум. Если НО не меньше 8 (без округления), то студент может не сдавать экзамен. В этом случае ИО = Округление(НО). Округление арифметическое.

Ведомость

БПМИ235	БПМИ236	БПМИ237	БПМИ238	БПМИ239	БПМИ2310	БПМИ2311	БПМИ2312

Сводная таблица с оценками по ДЗ

БПМИ235	БПМИ236	БПМИ237	БПМИ238	БПМИ239	БПМИ2310	БПМИ2311	БПМИ2312

Книги

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

1. Нестеренко Ю. В., Теория чисел
2. Акритас А.Г. Основы компьютерной алгебры с приложениями. 1994
3. Алфутова Н. Б., Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. М.: МЦНМО, 2018
4. Бухштаб А. А., Теория чисел
5. Виноградов И. М., Основы теории чисел.
6. Ноден П., Китте К. Алгебраическая алгоритмика
7. 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,