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

2025-03-19T15:57:16Z

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

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

== О курсе ==

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

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

=== Семинары ===

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

{| class="wikitable" style="text-align:center"
|-
! Группы !! [https://t.me/+WfE7TaEH2D0zMWUy БПМИ246] !! [https://t.me/+V_dH_uHMBUE4ODcy БПМИ247] !! [https://t.me/+ItyiDRJ9ufo5N2U6 БПМИ248] !! [https://t.me/+Vaqkfz1kLbs2MjIy БПМИ249] !! [https://t.me/+uPyWQ7rzkpBkYjg6 БПМИ2410] !! [https://t.me/+eTJpMRmNXjplOGRi БПМИ2411] !! [https://t.me/+Sf2gH4autYMwOTdi БПМИ2412] !! [https://t.me/+EnreJjWDOj9lNjRi БПМИ2413] !! [https://t.me/+OHPac94TX0szYTM6 БПМИ2414]
|-
!Лектор ||colspan="9"| [https://t.me/oleg_n_german О.Н. Герман]
|-
!Семинаристы !! [https://t.me/AlexeyVUstinov Устинов Алексей Владимирович] !! [https://t.me/oleg_n_german Герман Олег Николаевич] !![https://t.me/Vitalique_Iudelevich Юделевич Виталий Викторович] !! colspan="2" | [https://t.me/Artyom_Radomskii Радомский Артем Олегович] !! Чанга Марис Евгеньевич !! [https://t.me/Vitalique_Iudelevich Юделевич Виталий Викторович] !! Чанга Марис Евгеньевич !! [https://t.me/DmitryFrolenkov Фроленков Дмитрий Андреевич]
|-
! Ассистенты !! [https://t.me/mitseytlin Цейтлин Михаил Ильич] !! [https://t.me/uGAliok7 Гагарина Ульяна Юрьевна] !! [https://t.me/lizgbet Горбач Елизавета Леонидовна]!! [https://t.me/Oladiy2504 Копнев Максим Михайлович] !! [https://t.me/morz1k3 Токарев Алексей Михайлович] !! [https://t.me/alibaba_dushan Бабинский Георгий Олегович] !! [https://t.me/dd1ma Зорин Дмитрий Александрович] !! [https://t.me/the_overfeeling Герасимов Борис Александрович] !! [https://t.me/raspberru Грецкая Вера Ильинична]
|-
!Ассистент лектора || colspan="9"| [https://t.me/citizen_murad Агаев Мурад]
|}
<br/>

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

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

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

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

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

== Лекции ==

Лекция 1 (10.01.2025): Деление с остатком, алгоритм Евклида, конечные цепные дроби.

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

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

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

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

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

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

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

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

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

[https://disk.yandex.ru/i/xOO5KTVY8W1nHA Конспект лекций]

== Семинары ==

[https://disk.yandex.ru/i/zVz0Hewxu5u6oQ Семинар 1]

[https://disk.yandex.ru/i/tPaQpvfvKAy4tg Семинар 2]

[https://disk.yandex.ru/i/GJVCoMgYl6x7cg Семинар 3]

[https://disk.yandex.ru/i/e7gsRegrZJGPbg Семинар 4]

[https://disk.yandex.ru/i/4hPgqm8XuPAFmA Семинар 5]

[https://disk.yandex.ru/i/JcIjSaF0zDpeFg Семинар 6]

[https://disk.yandex.ru/i/mhAGHx2791yNxQ Семинар 7]

[https://disk.yandex.ru/i/bISRFe73cPCnGQ Семинар 8]

[https://disk.yandex.ru/i/TinAlAHHOfj-Bw Семинар 9]

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

[https://disk.yandex.ru/i/P-a-J-tketqafg ДЗ 1]

[https://disk.yandex.ru/i/mS3djEd09JJmAQ ДЗ 2]

[https://disk.yandex.ru/i/QCZp2tu7H7owFg ДЗ 3]

[https://disk.yandex.ru/i/bIleLoxfSloWbA ДЗ 4]

[https://disk.yandex.ru/i/J8FPvrJH8mZlxw ДЗ 5]

[https://disk.yandex.ru/i/gqLSRA6iqre5Lg ДЗ 6]

[https://disk.yandex.ru/i/HwhB4D7zhv8CuA ДЗ 7]

[https://disk.yandex.ru/i/mMW76woWPSm85A ДЗ 8]

[https://disk.yandex.ru/i/-w91LXyyrqjGXA ДЗ 9]

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

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

==== Распределение по аудиториям ====
R401 - БПМИ246, БПМИ247, БПМИ248

R201 - БПМИ249, БПМИ2410, БПМИ2411

R204 - БПМИ2412, БПМИ2413, БПМИ2414

[https://disk.yandex.ru/i/9b0ewjU1K9biFg Контрольная работа - демо-версия]

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

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

[https://disk.yandex.ru/i/f8EMKcHLup0nXA Программа курса]

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

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

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

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

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

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

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

{| class="wikitable" style="text-align:center"
|-
! colspan="2" | 21.03 Аудитория R204
|-
! Группа !! Время
|-
|| БПМИ249 || 13:30
|-
|| БПМИ246 || 15:30
|}

{| class="wikitable" style="text-align:center"
|-
! colspan="2" | 21.03 Аудитория R205
|-
! Группа !! Время
|-
|| БПМИ247 || 18.00
|}

{| class="wikitable" style="text-align:center"
|-
! colspan="2" | 22.03 Аудитория R401
|-
! Группа !! Время
|-
|| БПМИ2410 || 11:00
|-
|| БПМИ2411 || 12:30
|-
|| БПМИ2414 || 14:00
|-
|| БПМИ2413 || 16.00
|-
|| БПМИ248 || 17.30
|-
|| БПМИ2412 || 19.00
|}

== Экзамен ==

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

==== Распределение по аудиториям ====
R201 - БПМИ246, БПМИ247, БПМИ248, БПМИ249

R204 - БПМИ2410, БПМИ2411, БПМИ2412

R205 - БПМИ2413, БПМИ2414

[https://disk.yandex.ru/i/4nGLWlDRHG_jgA Экзамен - демо-версия]

== Оценка ==

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

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

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

== Ведомость ==
{| class="wikitable" style="text-align:center"
|-
! [https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=229551255#gid=229551255 БПМИ246]||[https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=724726636#gid=724726636 БПМИ247] !! [https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=2049186593#gid=2049186593 БПМИ248] !! [https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=183451133#gid=183451133 БПМИ249] !! [https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=867690546#gid=867690546 БПМИ2410] !![https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=593889813#gid=593889813 БПМИ2411] !! [https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=855095648#gid=855095648 БПМИ2412] !! [https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=466862776#gid=466862776 БПМИ2413] !! [https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=1874066094#gid=1874066094 БПМИ2414]
|}

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

{| class="wikitable" style="text-align:center"
|-
! [https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=1989747412#gid=1989747412 БПМИ246]||[https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=1443467987#gid=1443467987 БПМИ247] !! [https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=1258458558#gid=1258458558 БПМИ248] !! [https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=420770853#gid=420770853 БПМИ249] !! [https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=328306085#gid=328306085 БПМИ2410] !![https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=651319179#gid=651319179 БПМИ2411] !! [https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=1802675590#gid=1802675590 БПМИ2412] !! [https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=5883153#gid=5883153 БПМИ2413] !! [https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=849197000#gid=849197000 БПМИ2414]
|}

==Книги==
===Основная литература===
#[http://mmmf.msu.ru/lect/nesterenko/mainnth.pdf Нестеренко Ю. В., Теория чисел]
#[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 Ноден П., Китте К. Алгебраическая алгоритмика]
#[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]

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

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

Теория чисел (основной поток) 2024/25 - История изменений

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