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

О курсе

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

Группы	БПМИ256	БПМИ257	БПМИ258	БПМИ259	БПМИ2510	БПМИ2511	БПМИ2512	БПМИ2513	БПМИ2514	БПМИ2515
Лектор	О.Н. Герман
Семинаристы	Герман Олег Николаевич	Устинов Алексей Владимирович	Запрягаев Александр Александрович	Радомский Артем Олегович	Кухарчук Иван Андреевич	Юделевич Виталий Викторович		Чанга Марис Евгеньевич	Александров Кирилл Игоревич	Фроленков Дмитрий Андреевич
Ассистенты	Комарова Елизавета, Ван Петр	Ли Людмила, Акбарова Севинч	Гузаиров Тимур, Худжамов Асадбек	Босякова Яна, Бобоев Хилол	Дмитриев Андрей, Мамедов Африн	Грицан Максим, Лисиенко Данил	Комарова Елизавета, Мамедов Африн	Головачёва Мария, Бабинский Георгий	Соколов Матвей , Боженов Ростислав	Маликова Полина, Шмыгина Эмилия
Ассистент лектора	Грецкая Вера Ильинична

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

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

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

Всё должно быть написано аккуратно и понятно. Ассистент имеет право вызвать студента на защиту задания, если решение неясное или есть подозрение на списывание или использование ИИ. В случае неявки или невозможности объяснить решение студент получает 0 баллов.

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

Лекции

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

Лекция 2 (19.01.2026): Важная лемма (она же обобщённая лемма Евклида), основная теорема арифметики, линейные диофантовы уравнения от двух неизвестных, теорема Ламе о количестве делений с остатком в алгоритме Евклида.

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

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

Лекция 5 (09.02.2026): Лемма Гензеля и подъём решения, критерий Эйлера квадратичности вычета, определение символа Лежандра.

Лекция 6 (16.02.2026): Элементарные свойства символа Лежандра, лемма Гаусса о символе Лежандра, вывод формулы для символа Лежандра от двойки.

Лекция 7 (21.02.2026): Доказательство квадратичного закона взаимности Гаусса, символ Якоби и его свойства. Тест Соловея-Штрассена.

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

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

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

Конспект лекций 2025-го года

Лекция 02.02.2026

Лекция 20.02.2026

Лекция 06.03.2026

Конспект лекций 2026-го года

Семинары

Семинар 1

Семинар 2

Семинар 3

Семинар 4

Семинар 5

Семинар 6

Семинар 7

Семинар 8

Семинар 9

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

ДЗ 1

ДЗ 2

ДЗ 3

ДЗ 4

ДЗ 5

ДЗ 6

ДЗ 7

ДЗ 8

ДЗ 9

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

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

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

R201 - БПМИ256, БПМИ257, БПМИ258

R306 - БПМИ259, БПМИ2510

R401 - БПМИ2511, БПМИ2512, БПМИ2513

R504 - БПМИ2514, БПМИ2515

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

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

Коллоквиум

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

Коллоквиум состоится 20-го, 21-го и 23-го марта.

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

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

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

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

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

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

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

20.03 Аудитория R401
Группа	Время
БПМИ256	11:30
БПМИ259	13:30
БПМИ2514	15:00
БПМИ2515	16:30

21.03 Аудитория R204
Группа	Время
БПМИ2512	15:00
БПМИ257	16:30
БПМИ2513	18:00

23.03 Аудитория R305
Группа	Время
БПМИ2511	14:40
БПМИ258	16:20
БПМИ2510	17:30

Экзамен

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

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

R201 - БПМИ256, БПМИ257, БПМИ258, БПМИ259

R401 - БПМИ2510, БПМИ2511, БПМИ2512, БПМИ2513

R404 - БПМИ2514, БПМИ2515

Экзамен - демо-версия

Оценка

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

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

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

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

Ведомость

БПМИ256	БПМИ257	БПМИ258	БПМИ259	БПМИ2510	БПМИ2511	БПМИ2512	БПМИ2513	БПМИ2514	БПМИ2515

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

БПМИ256	БПМИ257	БПМИ258	БПМИ259	БПМИ2510	БПМИ2511	БПМИ2512	БПМИ2513	БПМИ2514	БПМИ2515

Книги

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

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,