imported>Ustinov: Migrated current public revision from wiki.cs.hse.ru

2026-03-28T14:15:17Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

== О курсе ==

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

=== Преподаватели и учебные ассистенты ===
{| class="wikitable" style="text-align:center"
|-
! Группа !! БПМИ251 !! БПМИ252 !! БПМИ253 !! БПМИ254 !! БПМИ255
|-
|| Лектор ||colspan="5"| [https://t.me/AlexeyVUstinov А.В. Устинов]
|-
|| Семинарист || [https://t.me/ozhegov57 Ожегов Фёдор Юрьевич] || [https://t.me/AlexeyVUstinov А.В. Устинов] ||colspan="2" | А. Калмынин || [https://t.me/ivbeldiev Бельдиев Иван Сергеевич]
|-
|| Ассистент || [https://t.me/pythonabuser Хорст Алина], [https://t.me/idtagirm Мухаметшин Тагир] || [https://t.me/Polushari Арзамасов Александр], [https://t.me/ndden Денисов Николай] || [https://t.me/gowentgone777 Архипов Виктор], [https://t.me/Anilaniklot Кравчук Илья] || [https://t.me/SanLokin Леонович Матвей ] , [https://t.me/bkaajf Контраталиев Алан] || [https://t.me/lizgbet Горбач Елизавета], [https://t.me/shannymad Полянская Софья]
|-
|| Ассистент лектора || colspan="5" | [https://t.me/raspberru Грецкая Вера Ильинична]
|-
|}

== Лекции ==

[https://drive.google.com/file/d/1fDBOjj4GL0S3D9hI8NTYvCfxBbuHLXj2/view?usp=sharing Обновляемый конспект.]

Лекция 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, Рабина, Эль-Гамаля и Гольдвассер -- Микали. Криптосистема Пэйе.

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

[https://drive.google.com/drive/folders/1ocvFGs00Xcj4p8gFyA_S3FMPE_se_UhC?usp=sharing Папка с материалами семинаров и ДЗ.]

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

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

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

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

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

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

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

[https://drive.google.com/file/d/115mzSDLriVxZEf8MMAx4TGIgvZrBU8iK/view?usp=sharing Демо-вариант.]

[https://us06web.zoom.us/j/82246748417?pwd=mJa8GZ9XoKGdloi2koXLMSZ18zbxwf.1 Ссылка] для пишущих онлайн.

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

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

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

== Коллоквиум ==

Дата: 21 марта. Время: 9:30-21:00. [https://drive.google.com/file/d/1cL35Kd-GbUoQSohLwnPMPm2v-2WKXrVj/view?usp=drive_link Программа.]

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

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

{| class="wikitable" style="text-align:center"
|-
! Группа !! Время
|-
||БПМИ254 || 9:30
|-
||БПМИ251 || 11:30
|-
||БПМИ252 || 13:00
|-
||БПМИ253 || 14:30
|-
||БПМИ255|| 16:30
|}

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

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

'''Билет''' будет состоять из следующих частей (максимально 9 баллов):
#два определения (по 1 баллу каждое);
#формулировки двух теорем без доказательства (по 1 баллу каждая);
#две теоремы с доказательствами (по 2.5 балла каждое).

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

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

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

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



== Экзамен ==

[https://drive.google.com/file/d/16sPt9nOa4Gy6-uCL3pD5ZmCPHlvwyDJy/view?usp=sharing Демо-версия]

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 (без округления), то студент может не сдавать экзамен. В этом случае ИО = Округление(НО).
Округление арифметическое.

== Ведомость ==
{| class="wikitable" style="text-align:center"
|-
! [https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=840627089#gid=840627089 БПМИ251] || [https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=1771040506#gid=1771040506 БПМИ252] || [https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=382422285#gid=382422285 БПМИ253]!![https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=538948281#gid=538948281 БПМИ254] !!
[https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=808431978#gid=808431978 БПМИ255]
|}

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

{| class="wikitable" style="text-align:center"
|-
! [https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=0#gid=0 БПМИ251] || [https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=61268542#gid=61268542 БПМИ252] || [https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=710162730#gid=710162730 БПМИ253]!! [https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=764991279#gid=764991279 БПМИ254] !! [https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=766813518#gid=766813518 БПМИ255]
|}

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

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

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

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

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

==Книги==
===Основная литература===
# [АР] [http://ega-math.narod.ru/Books/Ireland.htm Айерленд К. Роузен, М. Классическое введение в современную теорию чисел. - М.: Мир, 1998.]
# [A] [https://www.studmed.ru/akritas-ag-osnovy-kompyuternoy-algebry-s-prilozheniyami_4cf6c2ced74.html Акритас А.Г. Основы компьютерной алгебры с приложениями. 1994]
# [АУ] [https://uchebnik.mos.ru/system_2/atomic_objects/files/007/640/620/original/alfutova-ustinov-text.pdf Алфутова Н. Б., Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. М.: МЦНМО, 2018]
# [Б] [https://mahalex.net/151-153/Buchstab.pdf Бухштаб А. А., Теория чисел]
# [ВИМ] [https://math.ru/lib/book/djvu/vinogradov.djvu Виноградов И. М., Основы теории чисел.]
# [НК] [https://www.studmed.ru/noden-p-kitte-k-algebraicheskaya-algoritmika-s-uprazhneniyami-i-resheniyami-_dc06f6ef316.html Ноден П., Китте К. Алгебраическая алгоритмика]
# [MOV] [https://doc.lagout.org/network/3_Cryptography/CRC%20Press%20-%20Handbook%20of%20applied%20Cryptography.pdf Menezes A., Oorschot P. van, Vanstone S. Handbook of Applied Cryptography]

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

# [https://techlibrary.ru/b/2j1a1s1j1m1f1o1l1p_2w.2v._3a1f1p1r1f1t1j1l1p-1y1j1s1m1p1c2c1f_1a1m1d1p1r1j1t1n2c_1c_1l1r1j1q1t1p1d1r1a1v1j1j._2003.pdf Василенко, О. Н. Теоретико-числовые методы в криптографии МЦНМО, 2003]
# [ВЭБ] [https://mathprofi.com/uploads/files/2581_f_41_e.b.vinberg-kurs-algebry-2-e-izd.pdf Винберг Э. Б. Курс алгебры]
# Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012
# Гашков С. Б., Применко Э. А., Черепнев М. А. Криптографические методы защиты информации, Академия, 2010
# Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011
# Кнут, Д. Е. Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы "Вильямс" , М., Санкт-Петербург, Киев, 2000
# [http://lib.ysu.am/open_books/416134.pdf Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001.]
# [http://mmmf.msu.ru/lect/nesterenko/mainnth.pdf Нестеренко Ю. В., Теория чисел]
#[https://library.samdu.uz/files/5ef5e9f7c2b02d90200f92776db5bbc3_%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D0%BA%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8E_by_%D0%9F%D0%BE%D0%B4_%D0%BE%D0%B1%D1%89_%D1%80%D0%B5%D0%B4_%D0%AF%D1%89%D0%B5%D0%BD%D0%BA%D0%BE_%D0%92_%D0%92_2012.pdf Ященко, В. В. (ред.) Введение в криптографию, МЦНМО, Москва, 1999]
# Hoffstein, J.; Pipher, J., Silverman, J. H. An introduction to mathematical cryptography Springer, 2008,

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

imported>Ustinov: Migrated current public revision from wiki.cs.hse.ru