Теория чисел (основной поток) 2024/25 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показаны 33 промежуточные версии 2 участников)
Строка 17: Строка 17:
 
!Семинаристы !! [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/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/citizen_murad Агаев Мурад] !!  [https://t.me/the_overfeeling Герасимов Борис Александрович] !! [https://t.me/raspberru Грецкая Вера Ильинична]
+
  ! Ассистенты !!  [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 Агаев Мурад]
 
  !Ассистент лектора || colspan="9"| [https://t.me/citizen_murad Агаев Мурад]
Строка 48: Строка 48:
 
Лекция 5 (07.02.2025): Лемма Гензеля и подъём решения, критерий Эйлера квадратичности вычета, определение символа Лежандра.
 
Лекция 5 (07.02.2025): Лемма Гензеля и подъём решения, критерий Эйлера квадратичности вычета, определение символа Лежандра.
  
−
Лекция 6 (14.02.2025): Элементарные свойства символа Лежандра, лемма Гаусса о символе Лежандра, вывод формулы для символа Лежандра от двойки, доказательство квадратичного закона взаимности Гаусса.
+
Лекция 6 (14.02.2025): Элементарные свойства символа Лежандра, лемма Гаусса о символе Лежандра, вывод формулы для символа Лежандра от двойки.
  
−
Лекция 7 (21.02.2025): Символ Якоби и его свойства, тест Соловея-Штрассена.
+
Лекция 7 (21.02.2025): Доказательство квадратичного закона взаимности Гаусса, символ Якоби и его свойства.
  
−
Лекция 8 (28.02.2025):  
+
Лекция 8 (28.02.2025): Тест Соловея-Штрассена, доказательство теоремы о тесте Соловея-Штрассена, определение показателя вычета по модулю, делимость значения функции Эйлера на показатель, определение первообразного корня.
  
−
Лекция 9 (07.03.2025):  
+
Лекция 9 (07.03.2025): Мультипликативность функции Эйлера и явная формула для неё, теорема о количестве первообразных корней в приведённой системе вычетов, доказательство существования первообразных корней по простому модулю.
  
−
Лекция 10 (14.03.2025):  
+
Лекция 10 (14.03.2025): Критерий первообразности, описание модулей, по которым существуют первообразные корни, протокол Диффи-Хеллмана построения общего ключа шифрования, криптографическая система Эль-Гамаля.
  
−
[https://disk.yandex.ru/i/3X0IO6qfs_J-9A Первые шесть лекций]
+
[https://disk.yandex.ru/i/xOO5KTVY8W1nHA Конспект лекций]
  
 
== Семинары ==
 
== Семинары ==
Строка 73: Строка 73:
  
 
[https://disk.yandex.ru/i/JcIjSaF0zDpeFg Семинар 6]
 
[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]
  
 
== Домашние задания ==
 
== Домашние задания ==
Строка 87: Строка 93:
  
 
[https://disk.yandex.ru/i/gqLSRA6iqre5Lg ДЗ 6]
 
[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]
  
 
== Контрольная работа ==
 
== Контрольная работа ==
Строка 104: Строка 116:
  
 
== Коллоквиум ==
 
== Коллоквиум ==
 +
 +
[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 Экзамен - демо-версия]
 +
 
== Оценка ==
 
== Оценка ==
  
Строка 123: Строка 206:
  
 
== Ведомость ==
 
== Ведомость ==
 +
{| 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]
 +
|}
 +
 
== Сводная таблица с оценками по ДЗ ==
 
== Сводная таблица с оценками по ДЗ ==
  

Текущая версия на 18:57, 19 марта 2025

О курсе

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

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

Семинары

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

Группы БПМИ246 БПМИ247 БПМИ248 БПМИ249 БПМИ2410 БПМИ2411 БПМИ2412 БПМИ2413 БПМИ2414
Лектор О.Н. Герман
Семинаристы Устинов Алексей Владимирович Герман Олег Николаевич Юделевич Виталий Викторович Радомский Артем Олегович Чанга Марис Евгеньевич Юделевич Виталий Викторович Чанга Марис Евгеньевич Фроленков Дмитрий Андреевич
Ассистенты Цейтлин Михаил Ильич Гагарина Ульяна Юрьевна Горбач Елизавета Леонидовна Копнев Максим Михайлович Токарев Алексей Михайлович Бабинский Георгий Олегович Зорин Дмитрий Александрович Герасимов Борис Александрович Грецкая Вера Ильинична
Ассистент лектора Агаев Мурад


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

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

Конспект лекций

Семинары

Семинар 1

Семинар 2

Семинар 3

Семинар 4

Семинар 5

Семинар 6

Семинар 7

Семинар 8

Семинар 9

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

ДЗ 1

ДЗ 2

ДЗ 3

ДЗ 4

ДЗ 5

ДЗ 6

ДЗ 7

ДЗ 8

ДЗ 9

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

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

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

R401 - БПМИ246, БПМИ247, БПМИ248

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

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

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

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

Коллоквиум

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

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

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

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

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

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

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

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

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

21.03 Аудитория R204
Группа Время
БПМИ249 13:30
БПМИ246 15:30
21.03 Аудитория R205
Группа Время
БПМИ247 18.00
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

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

Оценка

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

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

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

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

Ведомость

БПМИ246 БПМИ247 БПМИ248 БПМИ249 БПМИ2410 БПМИ2411 БПМИ2412 БПМИ2413 БПМИ2414

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

БПМИ246 БПМИ247 БПМИ248 БПМИ249 БПМИ2410 БПМИ2411 БПМИ2412 БПМИ2413 БПМИ2414

Книги

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

  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,
Источник — «http://wiki.cs.hse.ru/index.php?title=Теория_чисел_(основной_поток)_2024/25&oldid=90247»