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

2024-03-28T17:41:27Z

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

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

== О курсе ==

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

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

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

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

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

{| class="wikitable" style="text-align:center"
|-
! Группы !! [https://t.me/+YcVFRwfqR9k5YzEy БПМИ235] !! [https://t.me/+pnNWj-79omkwMTVi БПМИ236] !! [https://t.me/+I9q7MBh1BeA5ZGYy БПМИ237] !! [https://t.me/+TX-rBrj8zdQwZGIy БПМИ238] !! [https://t.me/+88ItrccGaJdhOTdi БПМИ239] !![https://t.me/+V9UuyV6zn5ZiMTdi БПМИ2310] !! БПМИ2311 !! [https://t.me/+kmA6Cvk49741N2U6 БПМИ2312]
|-
!Лектор ||colspan="8"| [https://t.me/oleg_n_german О.Н. Герман]
|- [https://t.me/i_mihanya А. Калмынин]
!Семинаристы || [https://t.me/oleg_n_german О.Н. Герман] || [https://t.me/AlexeyVUstinov А.В. Устинов] || colspan="2" | А. Калмынин || М. Чанга || Д. Фроленков || colspan="2" | [https://t.me/Artyom_Radomskii А. Радомский]
|-
! Ассистенты || [https://t.me/the_overfeeling Герасимов Борис] || [https://t.me/valertions Смирнова Валерия] || [https://t.me/sashalavitskaya Лавицкая Александра] || [https://t.me/artempotarusov Потарусов Артём ] || [https://t.me/Alexxxey5 Воронко Алексей] || [https://t.me/raspberru Грецкая Вера] || [https://t.me/amadare14 Кокоева Мария] || [https://t.me/polusladkaya_13 Михнёнок Екатерина]
|-
!Ассистент лектора || colspan="8"| [https://t.me/citizen_murad Агаев Мурад]
|}
<br/>

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

В домашнем задании каждая задача оценивается в 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): Доказательство существования первообразных корней по простому модулю, протокол Диффи-Хеллмана построения общего ключа шифрования, криптографическая система Эль-Гамаля.

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

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

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

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

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

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

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

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

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

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

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

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

[https://disk.yandex.ru/i/QSGE_BYrqpjxAg ДЗ 1]

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

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

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

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

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

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

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

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

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

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

==== Распределение по аудиториям ====
R201 - БПМИ236, БПМИ239

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

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

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

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

[https://us06web.zoom.us/j/88695073042?pwd=behOcPWw7oxAlYi3U83u11I6lqlg7B.1 Ссылка] для тех, кто будет онлайн сдавать.

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

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

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

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

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

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

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

[https://us06web.zoom.us/j/81977127622?pwd=3eMV9P5kxofTvHXWUsBQqzyzWVxADv.1 Cсылка] для тех, кто будет онлайн сдавать. Начало 14:00.

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

{| class="wikitable" style="text-align:center"
|-
! Группа !! Время !! аудитория
|-
|| БПМИ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

[https://us06web.zoom.us/j/87313108157?pwd=yJ0ojfmGF5jZXRepjStwGpdaOZHPJz.1 Cсылка] для тех, кто будет онлайн сдавать.

[https://disk.yandex.ru/i/GSKK9I3IFwTgAQ Демо-вариант]

== Оценка ==

В течение года установлены следующие формы контроля:
* один письменный экзамен (ЭК), в сессию после модуля;
* одна письменная контрольная работа (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/1zZ26QYBG-lzvD5UtNQdDXpL-zjjsCMIVonj0IzYowNE/edit#gid=1892256028 БПМИ235] !! [https://docs.google.com/spreadsheets/d/1zZ26QYBG-lzvD5UtNQdDXpL-zjjsCMIVonj0IzYowNE/edit#gid=1099059872 БПМИ236] !! [https://docs.google.com/spreadsheets/d/1zZ26QYBG-lzvD5UtNQdDXpL-zjjsCMIVonj0IzYowNE/edit#gid=1087832155 БПМИ237] !! [https://docs.google.com/spreadsheets/d/1zZ26QYBG-lzvD5UtNQdDXpL-zjjsCMIVonj0IzYowNE/edit#gid=1429278133 БПМИ238] !! [https://docs.google.com/spreadsheets/d/1zZ26QYBG-lzvD5UtNQdDXpL-zjjsCMIVonj0IzYowNE/edit#gid=840627089 БПМИ239] !! [https://docs.google.com/spreadsheets/d/1zZ26QYBG-lzvD5UtNQdDXpL-zjjsCMIVonj0IzYowNE/edit#gid=524339368 БПМИ2310] !! [https://docs.google.com/spreadsheets/d/1zZ26QYBG-lzvD5UtNQdDXpL-zjjsCMIVonj0IzYowNE/edit#gid=568835149 БПМИ2311] !! [https://docs.google.com/spreadsheets/d/1zZ26QYBG-lzvD5UtNQdDXpL-zjjsCMIVonj0IzYowNE/edit#gid=1364135207 БПМИ2312]
|}

== Сводная таблица с оценками по ДЗ ==
{| class="wikitable" style="text-align:center"
|-
! [https://docs.google.com/spreadsheets/d/1U7DHKr7VDHd6omByHHFuoqLJBIuWTvU8er1tEkMbKT8/edit#gid=2126681499 БПМИ235] !! [https://docs.google.com/spreadsheets/d/1U7DHKr7VDHd6omByHHFuoqLJBIuWTvU8er1tEkMbKT8/edit#gid=1961152746 БПМИ236] !! [https://docs.google.com/spreadsheets/d/1U7DHKr7VDHd6omByHHFuoqLJBIuWTvU8er1tEkMbKT8/edit#gid=700731827 БПМИ237] !! [https://docs.google.com/spreadsheets/d/1U7DHKr7VDHd6omByHHFuoqLJBIuWTvU8er1tEkMbKT8/edit#gid=584336209 БПМИ238] !! [https://docs.google.com/spreadsheets/d/1U7DHKr7VDHd6omByHHFuoqLJBIuWTvU8er1tEkMbKT8/edit#gid=1969423455 БПМИ239] !! [https://docs.google.com/spreadsheets/d/1U7DHKr7VDHd6omByHHFuoqLJBIuWTvU8er1tEkMbKT8/edit#gid=489605604 БПМИ2310] !! [https://docs.google.com/spreadsheets/d/1U7DHKr7VDHd6omByHHFuoqLJBIuWTvU8er1tEkMbKT8/edit#gid=1214806244 БПМИ2311] !! [https://docs.google.com/spreadsheets/d/1U7DHKr7VDHd6omByHHFuoqLJBIuWTvU8er1tEkMbKT8/edit#gid=1579466964 БПМИ2312]
|}

==Книги==
===Основная литература===
#[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,

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

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