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

О курсе

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

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

Группа	БПМИ251	БПМИ252	БПМИ253	БПМИ254	БПМИ255
Лектор	А.В. Устинов
Семинарист	Ожегов Фёдор Юрьевич	А.В. Устинов	А. Калмынин		Бельдиев Иван Сергеевич
Ассистент	Хорст Алина, Мухаметшин Тагир	Арзамасов Александр, Денисов Николай	Архипов Виктор, Кравчук Илья	Леонович Матвей , Контраталиев Алан	Горбач Елизавета, Полянская Софья
Ассистент лектора	Грецкая Вера Ильинична

Лекции

Обновляемый конспект.

Лекция 1 (16.01.2026) Алгоритмы и их сложность. Сложность умножения и деления столбиком. Сложность алгоритма Евклида. Лемма о линейном представлении НОДа. Основная теорема арифметики. Определение группы. Примеры групп. Определение кольца. Примеры колец. Кольцо вычетов.

Лекция 2 (23.01.2026) Сравнения и их свойства. Полная и приведённая системы вычетов. Группа обратимых элементов кольца вычетов. Малая теорема Ферма и теорема Эйлера. Мультипликативные функции. Мультипликативность функции Эйлера. Тест "Ферма". Псевдопростые числа Ферма. Числа Кармайкла. Тест сильной псевдопростоты.

Лекция 3 (30.01.2026) Теорема Вильсона. Поле вычетов по простому модулю. Теорема Рабина (без доказательства). Симметричная криптография. Криптосистема Полига -- Хеллмана. Асимметричная криптография. Криптосистема RSA. Электронная подпись RSA. Гомоморфное шифрование. Слепая подпись RSA.

Лекция 4 (06.02.2026) Китайская теорема об остатках (КТО), три доказательства. Изоморфизмы групп и колец. Прямое произведение групп и колец. КТО как изоморфизм колец вычетов. Делители нуля. Многочлены над полем. Деление многочленов с остатком. Теорема Безу. Теорема о числе корней многочлена. Расширенный алгоритм Евклида для многочленов. Однозначность разложения на множители в кольце многочленов. КТО для многочленов. Связь с интерполяционным многочленом Лагранжа.

Лекция 5 (13.02.2026) Первообразные корни (ПК). Критерий ПК. Существование ПК по простому модулю. Существование ПК по модулю p^2. Существование ПК по модулю p^a. Существование ПК по модулю 2p^a.

Лекция 6 (20.02.2026) Индексы. Задача дискретного логарифмирования. Протокол Диффи -- Хеллмана. Вычислительная задача Диффи -- Хеллмана. Протокол Эль-Гамаля. Полиномиально сводимые и вычислительно эквивалентные функции. Вычислительная эквивалентность задач DH и EG. Трёхэтапный протокол Шамира. Квадратичные вычеты. Критерий Эйлера.

Лекция 7 (27.02.2026) Символ Лежандра. Простейшие свойства символа Лежандра. Критерий Гаусса. Квадратичный закон взаимности. Символ Якоби и его свойства. Теорема Лагранжа о порядке подгруппы (без доказательства). Тест Соловея -- Штрассена. Псевдопростые числа Эйлера.

Лекция 8 (06.03.2026) Оценка числа оснований, для которых тест Соловея -- Штрассена не срабатывает. Извлечение квадратного корня по модулю простого числа p=4k+3. Числа Блюма. Криптосистема Рабина, шифрование и электронная подпись. Эквивалентность задач факторизации числа Блюма n и извлечения квадратного корня по модулю n. Забывчивая передача Рабина. Протоколы привязки к биту и подбрасывания монеты по телефону. Подбрасывания монеты по телефону с помощью чисел Блюма.

Лекция 9 (13.03.2026) Криптосистема Гольдвассер -- Микали: протоколы привязки к биту и шифрования. Генератор Блюм -- Блюма -- Шуба. Вероятностное шифрование Блюма -- Гольдвассер. Лемма Гензеля. Подъём решений полиномиальных сравнений. р-адические числа.

Лекция 10 (20.03.2026) Гомоморфное шифрование. Гомоморфность криптосистем RSA, Рабина, Эль-Гамаля и Гольдвассер -- Микали. Криптосистема Пэйе.

Семинары и домашние задания

Папка с материалами семинаров и ДЗ.

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

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

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

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

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

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

Дата и время: 19.02 16:20-17:40. Аудитории R201 (251, 252), R401 (253, 254), R406 (255).

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

Ссылка для пишущих онлайн.

Правила контрольной работы

1. Разрешается принести с собой лист формата А4 с выписанными формулами (на одной стороне). Можно от руки написать на планшете и затем распечатать.

2. Разрешается принести с собой калькулятор.

Коллоквиум

Дата: 21 марта. Время: 9:30-21:00. Программа.

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

Коллоквиум будет проходить в аудитории R306.

Группа	Время
БПМИ254	9:30
БПМИ251	11:30
БПМИ252	13:00
БПМИ253	14:30
БПМИ255	16:30

Правила проведения коллоквиума

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

Билет будет состоять из следующих частей (максимально 9 баллов):

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

Если за ответ по билету было набрано 7,5-9 баллов, то студент имеет возможность запросить у проверяющего дополнительную сложную задачу (на 2 балла), которую проверяющий выбирает из списка дополнительных задач сам. Дополнительные задачи заранее не известны.
Замечание: Эта задача дается только в том случае, если студент набрал 7,5-9 баллов за все остальные части билета. Задача не прописана в билете, она выдается проверяющим.

Время подготовки билета На подготовку вопрос из билета (пунктов 1-3) 40 минут. Беседа с преподавателем идет не больше 40 минут. После беседы с преподавателем, если студент набирает 7,5-9 баллов, дается ещё до 20 минут на решение сложной задачи. Студент максимально может потратить 1 час и 45 минут на сдачу коллоквиума.

Оценка за коллоквиум равна минимуму из 10 и набранного числа баллов.

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

Экзамен

Демо-версия

30 марта 2026 г., 16:20-18:20. Аудитории R401, R503, R305, R306 = 240+110+108+84.

1. Разрешается принести с собой калькулятор (непрограммируемый).

Оценка

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

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

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

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

Ведомость

БПМИ251	БПМИ252	БПМИ253	БПМИ254	БПМИ255

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

БПМИ251	БПМИ252	БПМИ253	БПМИ254	БПМИ255

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

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

Теория чисел (пилотный_поток) 2024/25

Криптография на решётках 24/25 (факультатив, 4-й модуль 24/25 у.г.)

Дополнительные главы теории чисел (факультатив в 4-м модуле 22/23 у.г.)

Книги

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

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

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